Background: Exercise is beneficial for prostate cancer survivors. Therefore, understanding the mechanisms of physical activity (PA) behavior change is imperative. Purpose: The ENGAGE study was an exercise intervention for prostate cancer survivors, which improved vigorous physical activity (VPA) at postintervention and follow-up. The purpose of this study was to assess (a) whether the intervention improved social cognitive determinants of behavior and (b) the extent to which social cognitive determinants mediated the effect of the exercise intervention on VPA. Methods: Overall, 147 men consented to be involved in the study (intervention = 54, usual care = 93). Data from baseline, postintervention (12 weeks) and follow-up (6 months) were used in this analysis. Social cognitive determinants were measured using appropriate measures. VPA was measured using an adapted version of the Leisure-Time Exercise Questionnaire. Results: Compared with the control condition, men in the intervention condition had higher task self-efficacy postintervention (+16.23; 95% confidence interval [CI] +9.19 to +23.31; effect size [d] = 0.85, p < .001) and at follow-up (+12.58; 95% CI = +4.45 to +20.71, d = 0.50, p = .002). Task self-efficacy partially mediated the effect of the exercise intervention on VPA (indirect effect: B = 19.90; 95% CI 1.56 to 38.25, p = .033). Conclusion: The intervention improved the belief among prostate cancer survivors that they could perform challenging exercises for longer periods of time, which partially explained the positive effect of the intervention on VPA. Australia and New Zealand Clinical Trials Registration: ACTRN12610000609055.