<i>Objective:</i> We describe a model capable of predicting prostate cancer (PCa)-specific mortality up to 20 years after a radical prostatectomy (RP), which can adjust the predictions according to disease-free interval. <i>Patients and Methods:</i> 752 patients were treated with RP for organ-confined PCa. Cox regression modeled the probability of PCa-specific mortality. The significance of the predictors was confirmed in competing risks analyses, which account for other-cause mortality. <i>Results:</i> The mean follow-up was 11.4 years. The 5-, 10-, 15- and 20-year actuarial rates of PCa-specific survival were 99.0, 95.5, 90.9 and 85.7%, respectively. RP Gleason sum (p < 0.001), pT stage (p = 0.007), adjuvant radiotherapy (p = 0.03) and age at RP (p = 0.004) represented independent predictors of PCa-specific mortality in the Cox regression model as well as in competing risks regression. Those variables, along with lymph node dissection status (p = 0.4), constituted the nomogram predictors. After 200 bootstrap resamples, the nomogram achieved 82.6, 83.8, 75.0 and 76.3% accuracy in predicting PCa-specific mortality at 5, 10, 15 and 20 years post-RP, respectively. <i>Conclusions:</i> At 20 years, roughly 20% of men treated with RP may succumb to PCa. The current nomogram helps to identify these individuals. Their follow-up or secondary therapies may be adjusted according to nomogram predictions.