Background: Although clinical correlates can help predict biochemical failure (BF), genomic correlates have yet to be identified. We hypothesized there would exist genomic profiles in patients who experience BF after radical prostatectomy (RP), for whom aggressive regional therapy may be more appropriate. Methods: Genes of interest were identified using the 25 most commonly mutated genes from the COSMIC dataset. The Cancer Genome Atlas (TCGA) was used to study normalized microarray gene expression data for patients who underwent RP for treatment of Gleason 7-10, T1/T2 N0 prostate adenocarcinoma. BF was considered PSA > 0.1 following prostatectomy. Clinical data of interest included age, pre-treatment PSA, Gleason score, pathologic T stage, and country of origin. A multi-level hierarchical logistic regression model clustered with random effects by pathologic T stage and country of origin was built to identify predictors of BF. Variances were used to estimate how genomic differences explained differences in BF. Results: We identified 296 patients with T1/T2 N0 prostate adenocarcinoma who underwent RP. Median age was 60 with a median follow up of 2.3 years. 59% (n = 177) had Gleason 7 disease and 54% (n = 154) had T1 disease. 40.8% (n = 121) of patients had BF following RP. After adjusting for clinical covariates, 4 genes were associated with differences in BF. Specifically, increased RNA expression of E2F3 (OR 1.11 p < .001), CTNNB1 (OR 1.49, p = .002), and AR (OR 1.21, p < .001) were seen in patients who experienced BF. Expression of TP53 (OR 0.75, p < .001) and Gleason 7 disease (OR 0.62 vs. Gleason 8-10, p < .001) were associated with decreased likelihood of BF. Clustering by pathologic T stage accounted for 10% of variance in BF indicating that the 4 genes augment clinical patient characteristics. Conclusions: Genomic data augments pre-treatment clinical data in the stratification of patients undergoing RP. RNA expression of E2F3, CTNNB1, AR and TP53 is associated with differences in BF following RP. Clinically, these genes could aid in identifying patients who may benefit from more aggressive therapy. Further studies of the relationship between these genes and the development of prostate cancer could aid in future targeted therapies.