Information is limited on the influence of a change in fitness and/or physical activity on mortality in cardiac patients who undergo exercise rehabilitation. This was studied in 6,956 men (4,713 with myocardial infarctions, 2,243 who underwent coronary bypass surgery) completing a 12-month walking-based training regimen and followed for a median of 9 years (range 4 to 26; 67,820 patient-years). Peak oxygen uptake (VO2peak) was measured at the beginning and the end of the program, and walking distance and pace were recorded weekly. These and other pertinent data were entered into a Cox proportional-hazards model and tested for associations with time to cardiac and all-cause death. In total, 2,016 deaths were recorded (737 cardiac, 1,279 all-cause). The mean increase in VO2peak was 4.9 ml/kg/min (95% confidence interval [CI] 4.7 to 5.0, p <0.0001), and the mean increase in distance walked was 2.1 mi (95% CI 2.0 to 2.1, p <0.0001). Increase in VO2peak was significant on univariate analysis (hazard ratio [HR] 0.98) but not on multivariate analysis. Distance increase was a significant predictor of cardiac and all-cause death on multivariate analysis, with each 1-mi improvement conferring a 20% reduction in cardiac death (HR 0.80, 95% CI 0.71 to 0.87, p <0.0001). When categorized into groups of <1.3 (referent), 1.3 to 2.8, and >2.8 mi, increased walking distance of 1.3 to 2.8 and of >2.8 mi yielded 24% (HR 0.76, 95% CI 0.62 to 0.92, p = 0.005) and 48% (HR 0.52, 95% CI 0.40 to 0.68, p <0.0001) reductions in cardiac death, respectively. In conclusion, in men who underwent an exercise rehabilitation program, improvement in walking distance was a strong independent predictor, and a greater guide to prognosis, than gains in VO2peak.