Current prostate cancer risk classifications rely on clinicopathological parameters resulting in uncertainties for prognostication. To improve individual risk stratification, we examined the predictive value of selected proteins with respect to tumor heterogeneity and genomic instability. We assessed the degree of genomic instability in 50 radical prostatectomy specimens by DNA-Image-Cytometry and evaluated protein expression in related 199 tissue-microarray (TMA) cores. Immunohistochemical data of SATB1, SPIN1, TPM4, VIME and TBB5 were correlated with the degree of genomic instability, established clinical risk factors and overall survival. Genomic instability was associated with a GS >= 7 (p = 0.001) and worse overall survival (p = 0.008). A positive SATB1 expression was associated with a GS <= 6 (p = 0.040), genomic stability (p = 0.027), and was a predictor for increased overall survival (p = 0.023). High expression of SPIN1 was also associated with longer overall survival (p = 0.048) and lower preoperative PSA-values (p = 0.047). The combination of SATB1 expression, genomic instability, and GS lead to a novel Prostate Cancer Prediction Score (PCP-Score) which outperforms the current D'Amico et al. stratification for predicting overall survival. Low SATB1 expression, genomic instability and GS >= 7 were identified as markers for poor prognosis. Their combination overcomes current clinical risk stratification regimes.