Cardiac rehabilitation (CR) is recommended to improve exercise capacity after heart transplantation (HTx); however, the effects of marginal donor factors are unclear. Forty-one recipients participated in a 3-month CR program early after HTx (mean age 39 ± 14 years; 88% male). Patients were divided into marginal (≥ 2 marginal donor factors; n = 24) and control groups (< 2 marginal donor factors; n = 17). We examined donor and recipient factors related to change in peak oxygen uptake (peak VO₂) during the CR program using multiple linear regression analysis. Baseline characteristics were similar between groups, although the mean age was higher in the marginal group (43 ± 13 vs. 34 ± 14 years, p = 0.043). Peak VO₂ and knee extensor muscular strength (KEMS) improved significantly in both groups (p < 0.05), but there were no observed inter-group differences. Multiple analysis revealed change in KEMS (β = 0.52, 95% CI = 0.023–1.01) as an independent predictor of change in peak VO₂ after adjustment for recipients’ age, sex, and CR attendance frequency (adjusted R² = 0.25, p = 0.0084), whereas marginal donor factors were not a predictor (p = 0.76). The CR program improved exercise capacity in HTx recipients regardless of marginal donor factors, suggesting that recipients of marginal donor hearts should be referred to CR programs.