Although high body mass index (BMI) is associated with improved outcomes in established heart failure (HF), the impact of cardiorespiratory fitness on this obesity paradox is less clear. We studied 1,675 patients with systolic HF who underwent cardiopulmonary exercise testing at a single university center (77.4% men, mean age 52.2 ± 11.6 years, mean left ventricular ejection fraction 23.2 ± 7.1% and New York Heart Association class III or IV in 79.1%). We evaluated 2-year survival in patients stratified by both BMI (normal 18.5 to 24.9 kg/m²[reference], overweight 25 to 29.9 kg/m², obese ≥30.0 kg/m²) and by peak oxygen uptake (PKVO₂; high >14 ml/kg/minute, low ≤14 ml/kg/minute). At 2 years, BMI category was significantly associated with outcomes for the low PKVO₂ group (p <0.001) but not the high PKVO₂ group (p = 0.1). In the low PKVO₂ group, obese patients had decreased risk of death free from urgent status 1A heart transplant or ventricular assist device placement after multivariate adjustment compared with normal BMI (hazard ratio [HR] 0.64, 95% confidence interval [CI] 0.44 to 0.91, p = 0.01); no significant difference was observed for overweight patients (HR 0.91, 95% CI 0.66 to 1.25, p = 0.5). In the high PKVO₂ group, no relation was seen (overweight BMI HR 0.75, 95% CI 0.43 to 1.32, p = 0.3; obese HR 0.87, 95% CI 0.43 to 1.75, p = 0.7). In conclusion, the obesity paradox was only observed in patients with lower cardiorespiratory fitness in this advanced systolic HF cohort, indicating that improved functional capacity may attenuate the obesity paradox.