Background: Validated biomarkers can improve risk stratification for men with prostate cancer (PCa). A biopsy-based RT-PCR assay that provides a GPS (scale 0-100) has been validated as an independent predictor of adverse surgical pathology and BCR after RP in men with low-risk and low-volume intermediate-risk PCa. We sought to confirm that GPS is a predictor of BCR across the full spectrum of clinical risk (low, intermediate and high) in a large cohort of men with long term follow up within Kaiser Permanente Northern California (KPNC). Methods: From the KPNC clinical database of 6,184 RP treated men diagnosed with NCCN very low, low, intermediate and high-risk PCa between 1995- 2010, we performed a retrospective cohort study using stratified cohort sampling. BCR was defined as either 2 successive post-RP PSAs ≥ 0.2, or initiation of salvage therapy after a rising PSA ≥ 0.1. Archival biopsy tissue was assayed to yield a GPS. Univariable and multivariable Cox proportional hazards models were used to estimate the association, accounting for sampling weights and covariates. Results: Tissue was retrieved for 334 patients. 279 met all eligibility criteria and 259 (93%) generated a valid GPS. The cohort consisted of 117 BCR and 142 non-BCR events. GPS was strongly associated with BCR - HR/20 GPS units = 2.5; p < 0.0001 in univariable analysis, and after adjusting for PSA, clinical T stage and central biopsy Gleason Score (HR/20 units = 2.1; p = 0.002). The association between GPS and BCR was similar within different racial groups. Each of the 4 gene groups in GPS contributed to the prediction of BCR. Conclusions: GPS was associated with BCR independently of other clinical factors in surgically treated men with PCa, and may provide improved risk stratification beyond clinical risk assessment.