To identify candidate genes relevant for prostate tumour prognosis and progression, we performed an exhaustive gene search in seven previously described genomic-profiling studies of 161 prostate tumours, and four expression profiling studies of 61 tumours. From the resulting list of candidate genes, six were selected for protein-expression analysis based on the availability of antibodies applicable to paraffinised tissue: fatty acid synthase (FASN), MYC, β-adrenergic receptor kinase 1 (BARK1, GRK2) the catalytic subunits of protein phosphatases PP1α (PPP1CA) and PP2A (PPP2CB) and metastasis suppressor NM23-H1. These candidates were analysed by immunohistochemistry (IHC) on a tissue microarray containing 651 cores of primary prostate cancer samples and benign prostatic hyperplasias (BPH) from 175 patients. In univariate analysis, expression of PP1α (P= 0.001) was found to strongly correlate with Gleason score. MYC immunostaining negatively correlated with both pT-stage and Gleason score (P< 0.001 each) in univariate as well as in multivariate analysis. Furthermore, a subgroup of patients with high Gleason scores was characterised by a complete loss of BARK1 protein (P= 0.023). In conclusion, our study revealed novel molecular markers of potential diagnostic and therapeutic relevance for prostate carcinoma.