Background: Obesity and weight gain after the diagnosis of prostate cancer are associated with an increased risk of prostate cancer recurrence and mortality; individualized plans to help prostate cancer survivors maintain or lose weight may be beneficial for recurrence risk reduction. Herein, we explore whether gains in cardiovascular fitness predict successful weight loss in men participating in a weight loss trial (NCT01886677). Methods: Forty men were randomized to receive twice-weekly in-person and telephone-based guidance on calorie-restricted diets and aerobic exercise to promote ~0.91 kg/week weight loss, or wait-list control. Thirty-two men completed submaximal VO2 Treadmill Tests (TT), anthropometric measures and two 24-hour dietary recalls at baseline and follow-up. For this secondary analysis, study arms were combined and associations between baseline and longitudinal changes in physiological effort (PE, measured by heart rate during TT), predicted VO2max, caloric intake and weight loss were analyzed. Results: Men lost 3.4 kg in 50 ± 23 days on the study. Multivariate linear regression indicated weight change was associated with change in PE at stage 2TT (Partial R = 0.635, p < 0.001), days on study (Partial R = -0.589, p = 0.002) and change in caloric intake (Partial R = 0.457, p = 0.019). Conclusions: Untrained men experiencing elevated heart rates during stage 2TT at baseline were able to achieve greater weight loss over the study period; this association was strengthened by a decrease in PE at the same level from baseline to follow-up concomitant with reduced caloric intake. Therefore, for these middle-aged and older men with lower aerobic fitness, exercise appears to be a key factor in achieving higher degrees of weight loss.