Purpose: High-dose-rate brachytherapy (HDR-BT) for dose escalation in localized prostate cancer has been established as one standard treatment option. However, long-term results at followup (FU) ≥5 years are usually needed to ensure robustness of reported outcomes. Potential benefit of salvage therapy is, nevertheless, higher when relapse is diagnosed early. This study aimed to solve this dilemma by evaluating the prostate-specific antigen (PSA) nadir for early prediction of long-term biochemical control. Methods and Materials: Combined pelvis-external beam radiation/HDR-BT boost to EQD2 >100 Gy (α/β = 3) was performed in 459 consecutively treated patients. These patients with an FU ≥ 24 months were analyzed and stratified in PSA nadir (nPSA)-groups by PSA nadir within 18 months after radiotherapy (nPSA18). Kaplan–Meier/log-rank tests and Cox-regression models were used to compare the study endpoints. Results: The mean FU was 77 months. A PSA nadir within 18 months (nPSA18) <0.5 ng/mL was achieved in 222 patients with median time to reach nPSA18 of 7 months. The 5-year American Society of Therapeutic Radiology and Oncology (ASTRO) biochemical control (prostate-specific antigen disease-free survival) for the nPSA18 group <0.5 ng/mL was 89% and for the group ≥ 0.5 ng/mL, it was 78.6% (p = 0.011). nPSA18 was an independent predictor of cancer-specific survival, distant metastasis-free survival, and biochemical control (ASTRO) (p = 0.026, p = 0.020, and p = 0.01, respectively). Conclusions: The present results suggest that the PSA nadir level within 18 months after radiotherapy may serve as an early parameter for long-term biochemical control according to ASTRO definitions following radical dose escalation by HDR-BT for prostate cancer. Excellent outcomes were associated with nPSA18 < 0.5 ng/mL.