The purpose of this study was to investigate which patient characteristics may predict training effects on maximal and submaximal exercise performance in patients with heart failure. Together with commonly used clinical and performance-related variables, oxygen uptake kinetics during exercise recovery were included as possible predictors. Fifty patients with heart failure (New York Heart Association class II or III) performed a 12-week training program (cycle interval and resistance training). Training effects were expressed as changes in peak oxygen uptake (Vo2), Vo2 at ventilatory threshold (VT), and the time constant of Vo2 recovery after submaximal exercise (τ-rec). After training, peak Vo2, Vo2 at VT, and τ-rec improved significantly, with a wide variety in training responses. Changes in peak Vo2 were related to changes in VT (r = 0.79, p <0.001), but both changes were not related to changes in τ-rec. Using multivariate regression analyses, post-training changes in peak Vo2 could be predicted by recovery halftime of peak Vo2 (T1/2), peak Vo2 (percentage of predicted), and peak respiratory exchange ratio (R2 = 36%). Post-training changes in VT could be predicted by T1/2 and VT (predicted) (R2 = 29%), whereas changes in τ-rec could be predicted only by τ-rec at baseline (R2 = 34%). In conclusion, oxygen recovery kinetics after maximal and submaximal exercise substantially add to the prediction of training effects in patients with heart failure, presumably because of their relations with, respectively, central and peripheral impairments of exercise capacity. However, the explained variance in training effects is not sufficient to make a definite distinction between training responders and nonresponders.