Background There has been substantial increase in use of androgen deprivation therapy as adjuvant management of prostate cancer. However, this leads to a range of musculoskeletal toxicities including reduced bone mass and increased skeletal fractures compounded with rapid metabolic alterations, including increased body fat, reduced lean mass, insulin resistance and negative lipoprotein profile, increased incidence of cardiovascular and metabolic morbidity, greater distress and reduced quality of life. Numerous research studies have demonstrated certain exercise prescriptions to be effective at preventing or even reversing these treatment toxicities. However, all interventions to date have been of rehabilitative intent being implemented after a minimum of 3 months since initiation of androgen deprivation, by which time considerable physical and psychological health problems have manifested. The pressing question is whether it is more efficacious to commence exercise therapy at the same time as initiating androgen deprivation, so treatment induced adverse effects can be immediately attenuated or indeed prevented. Methods/design We are proposing a multi-site randomized controlled trial with partial crossover to examine the effects of timing of exercise implementation (immediate or delayed) on preserving long-term skeletal health, reversing short- and long-term metabolic and cardiovascular risk factors, and supporting mental health in men receiving androgen deprivation therapy. 124 men who are about to initiate androgen deprivation for prostate cancer will be randomized to immediate or delayed groups. Immediate will commence a 6-month exercise program within 7-10 days of their first dose. Delayed will receive usual care for 6 months and then commence the exercise program for 6 months (partial cross-over). Immediate will be free to adopt the lifestyle of their choosing following the initial 6-month intervention. Measurements for primary and secondary endpoints will take place at baseline, 6 months and 12 months. Discussion This project is unique as it explores a fundamental question of when exercise implementation will be of most benefit and addresses both physical and psychological consequences of androgen deprivation initiation. The final outcome may be adjunct treatment which will reduce if not prevent the toxicities of androgen deprivation, ultimately resulting in reduced morbidity and mortality for men with prostate cancer.