Background Androgen-deprivation therapy is offered to men with prostate cancer who have a rising prostate-specific antigen after curative therapy (PSA relapse) or who are considered not suitable for curative treatment; however, the optimal timing for its introduction is uncertain. We aimed to assess whether immediate androgen-deprivation therapy improves overall survival compared with delayed therapy. Methods In this randomised, multicentre, phase 3, non-blinded trial, we recruited men through 29 oncology centres in Australia, New Zealand, and Canada. Men with prostate cancer were eligible if they had a PSA relapse after previous attempted curative therapy (radiotherapy or surgery, with or without postoperative radiotherapy) or if they were not considered suitable for curative treatment (because of age, comorbidity, or locally advanced disease). We used a database-embedded, dynamically balanced, randomisation algorithm, coordinated by the Cancer Council Victoria, to randomly assign participants (1:1) to immediate androgen-deprivation therapy (immediate therapy arm) or to delayed androgen-deprivation therapy (delayed therapy arm) with a recommended interval of at least 2 years unless clinically contraindicated. Randomisation for participants with PSA relapse was stratified by type of previous therapy, relapse-free interval, and PSA doubling time; randomisation for those with non-curative disease was stratified by metastatic status; and randomisation in both groups was stratified by planned treatment schedule (continuous or intermittent) and treatment centre. Clinicians could prescribe any form and schedule of androgen-deprivation therapy and group assignment was not masked. The primary outcome was overall survival in the intention-to-treat population. The trial closed to accrual in 2012 after review by the independent data monitoring committee, but data collection continued for 18 months until Feb 26, 2014. It is registered with the Australian New Zealand Clinical Trials Registry (ACTRN12606000301561) and ClinicalTrials.gov (NCT00110162). Findings Between Sept 3, 2004, and July 13, 2012, we recruited 293 men (261 with PSA relapse and 32 with non-curable disease). We randomly assigned 142 men to the immediate therapy arm and 151 to the delayed therapy arm. Median follow-up was 5 years (IQR 3·3–6·2) from the date of randomisation. 16 (11%) men died in the immediate therapy arm and 30 (20%) died in the delayed therapy arm. 5-year overall survival was 86·4% (95% CI 78·5–91·5) in the delayed therapy arm versus 91·2% (84·2–95·2) in the immediate therapy arm (log-rank p=0·047). After Cox regression, the unadjusted HR for overall survival for immediate versus delayed arm assignment was 0·55 (95% CI 0·30–1·00; p=0·050). 23 patients had grade 3 treatment-related adverse events. 105 (36%) men had adverse events requiring hospital admission; none of these events were attributable to treatment or differed between treatment-timing groups. The most common serious adverse events were cardiovascular, which occurred in nine (6%) patients in the delayed therapy arm and 13 (9%) in the immediate therapy arm. Interpretation Immediate receipt of androgen-deprivation therapy significantly improved overall survival compared with delayed intervention in men with PSA-relapsed or non-curable prostate cancer. The results provide benchmark evidence of survival rates and morbidity to discuss with men when considering their treatment options. Funding Australian National Health and Medical Research Council and Cancer Councils, The Royal Australian and New Zealand College of Radiologists, Mayne Pharma Australia.