Objectives: (i) To assess whether exercise training attenuates the adverse effects of treatment in patients with newly diagnosed prostate cancer beginning androgen-deprivation therapy (ADT), and (ii) to examine whether exercise-induced improvements are sustained after the withdrawal of supervised exercise. Patients and Methods: In all, 50 patients with prostate cancer scheduled for ADT were randomised to an exercise group (n = 24) or a control group (n = 26). The exercise group completed 3 months of supervised aerobic and resistance exercise training (twice a week for 60 min), followed by 3 months of self-directed exercise. Outcomes were assessed at baseline, 3- and 6-months. The primary outcome was difference in fat mass at 3-months. Secondary outcomes included: fat-free mass, cardiopulmonary exercise testing variables, QRISK ®2 (ClinRisk Ltd, Leeds, UK) score, anthropometry, blood-borne biomarkers, fatigue, and quality of life (QoL). Results: At 3-months, exercise training prevented adverse changes in peak O 2 uptake (1.9 mL/kg/min, P = 0.038), ventilatory threshold (1.7 mL/kg/min, P = 0.013), O 2 uptake efficiency slope (0.21, P = 0.005), and fatigue (between-group difference in Functional Assessment of Chronic Illness Therapy-Fatigue score of 4.5 points, P = 0.024) compared with controls. After the supervised exercise was withdrawn, the differences in cardiopulmonary fitness and fatigue were not sustained, but the exercise group showed significantly better QoL (Functional Assessment of Cancer Therapy-Prostate difference of 8.5 points, P = 0.034) and a reduced QRISK2 score (−2.9%, P = 0.041) compared to controls. Conclusion: A short-term programme of supervised exercise in patients with prostate cancer beginning ADT results in sustained improvements in QoL and cardiovascular events risk profile.