Although ~40% of screen-detected prostate cancers (PCa) are indolent, advanced-stage PCa is a lethal disease with 5-year survival rates around 29%. Identification of biomarkers for early detection of aggressive disease is a key challenge. Starting with 52 candidate biomarkers, selected from existing PCa genomics datasets and known PCa driver genes, we used targeted mass spectrometry to quantify proteins that significantly differed in primary tumors from PCa patients treated with radical prostatectomy (RP) across three study outcomes: (i) metastasis ≥1-year post-RP, (ii) biochemical recurrence ≥1-year post-RP, and (iii) no progression after ≥10 years post-RP. Sixteen proteins that differed significantly in an initial set of 105 samples were evaluated in the entire cohort (n = 338). A five-protein classifier which combined FOLH1, KLK3, TGFB1, SPARC, and CAMKK2 with existing clinical and pathological standard of care variables demonstrated significant improvement in predicting distant metastasis, achieving an area under the receiver-operating characteristic curve of 0.92 (0.86, 0.99, p = 0.001) and a negative predictive value of 92% in the training/testing analysis. This classifier has the potential to stratify patients based on risk of aggressive, metastatic PCa that will require early intervention compared to low risk patients who could be managed through active surveillance.