To evaluate the temporal relationship between interval to biochemical recurrence (BCR) following radical prostatectomy (RP) and prostate cancer-specific mortality (PCSM).The study comprised of 2,116 men from the Victorian Radical Prostatectomy Register, a whole-of-population database of all RPs performed between 1995 and 2000 in Victoria, Australia. Follow-up prostate-specific antigen and death data were obtained via record linkage to pathology laboratories and the Victorian Registry of Births, Deaths and Marriages. Poisson regression models with PCSM as the outcome were fit to the data. Models included age at surgery, Gleason score and tumour stage as covariates.Median post-surgery and post-BCR follow-up was 10.3 and 7.5 years, respectively. 695 men (33 %) experienced BCR during follow-up, of which 82 % occurred within 5 years of RP; 66 men died from prostate cancer. Men with combined high Gleason sum (≥4 + 3) and extra-prostatic (≥pT3a) disease had substantially increased mortality rate with early BCR, while those experiencing BCR after a longer interval had significantly lower mortality. Men with combined low Gleason sum (≤3 + 4) and organ-confined disease (≤pT2c) risk disease were not at any substantial risk of death in this time frame regardless of timing of BCR following RP.This study evaluates the temporal relationship between BCR and PCSM using a whole-of-population cohort of men treated with RP. Men with low-risk features of prostate cancer at time of RP have low mortality even if they experience early BCR. This subgroup may be counselled regarding their favourable long-term prognosis.