Background: Impaired cardiorespiratory fitness (CRF) is a hallmark of heart failure (HF). Serum levels of C-reactive protein (CRP), a systemic inflammatory marker, and of N-terminal pro-brain natriuretic peptide (NT-proBNP), a biomarker of myocardial strain, independently predict adverse outcomes in HF patients. Whether CRP and/or NT-proBNP also predict the degree of CRF impairment in HF patients across a wide range of ejection fraction is not yet established. Methods: Using retrospective analysis, 200 patients with symptomatic HF who completed one or more treadmill cardiopulmonary exercise tests (CPX) using a symptom-limited ramp protocol and had paired measurements of serum high-sensitivity CRP and NT-proBNP on the same day were evaluated. Univariate and multivariate correlations were evaluated with linear regression after logarithmic transformation of CRP (log10) and NT-proBNP (logN). Results: Mean age of patients was 57 ± 10 years and 55% were male. Median CRP levels were 3.7 [1.5–9.0] mg/L, and NT-proBNP levels were 377 [106–1,464] pg/ml, respectively. Mean peak oxygen consumption (peak VO2) was 16 ± 4 mlO2•kg−1•min−1. CRP levels significantly correlated with peakVO2 in all patients (R = −0.350, p < 0.001) and also separately in the subgroup of patients with reduced left ventricular ejection fraction (LVEF) (HFrEF, N = 109) (R = −0.282, p < 0.001) and in those with preserved EF (HFpEF, N = 57) (R = −0.459, p < 0.001). NT-proBNP levels also significantly correlated with peak VO2 in all patients (R = −0.330, p < 0.001) and separately in patients with HFrEF (R = −0.342, p < 0.001) and HFpEF (R = −0.275, p = 0.032). CRP and NT-proBNP did not correlate with each other (R = 0.05, p = 0.426), but independently predicted peak VO2 (R = 0.421, p < 0.001 and p < 0.001, respectively). Conclusions: Biomarkers of inflammation and myocardial strain independently predict peak VO2 in HF patients. Anti-inflammatory therapies and therapies alleviating myocardial strain may independently improve CRF in HF patients across a large spectrum of LVEF.