Changes in prostate-specific antigen (PSA) values are often reported as velocity or doubling time. We compared the association of these two calculations—at the time of PSA failure after primary treatment for prostate cancer—with prostate cancer mortality. From a source population of 1313 US Veterans with prostate cancer, including 623 treated with curative intent, the study population included 242 men experiencing biochemical failure, 81 after surgery and 161 after radiation therapy. Clinically relevant calculations of PSA velocity (linear slope) and PSA doubling time (logarithmic slope) were assessed for their association with 11–16 years of mortality from prostate cancer. Death due to prostate cancer occurred in 52/242 (21.5%) men. Among men receiving surgery, PSA velocity ≥1.0 ng/mL/year was associated with increased prostate cancer mortality (HR=4.2, p value=0.037), whereas doubling time ≤12 months did not confer risk (HR=1.0, p value=0.95). Conversely, among patients receiving radiation therapy, doubling time ≤12 months was associated with increased prostate cancer mortality (HR=2.4, p value=0.049), but velocity did not confer a statistically significant risk (HR=3.8, p value=0.19). When assessing risk of prostate cancer mortality, PSA velocity can be more predictive after surgery and PSA doubling time can be more predictive after radiation therapy.