Protein phosphatase 1 nuclear-targeting subunit (PNUTS) is ubiquitously expressed and associates with PTEN and protein phosphatase 1 (PP1) to control its activity. The role of PNUTS overexpression has hardly been studied in cancer. In this study, we used immunohistochemistry to quantitate PNUTS expression on a tissue microarray containing 17,747 clinical prostate cancer specimens. As compared to normal prostate epithelium, PNUTS expression was often higher in cancer. Among 12,235 interpretable tumors, PNUTS staining was negative in 21%, weak in 34%, moderate in 35%, and strong in 10% of cases. High PNUTS expression was associated with higher tumor stage, classical and quantitative Gleason grade, nodal stage, surgical margin, Ki67 labeling index, and early biochemical recurrence (p < 0.0001 each). PNUTS expression proved to be a moderate prognostic parameter with a maximal univariable Cox proportional hazard for PSA recurrence-free survival of 2.21 compared with 5.91 for Gleason grading. It was independent from established prognostic parameters in multivariable analysis. Comparison with molecular data available from earlier studies using the same TMA identified associations between high PNUTS expression and elevated androgen receptor expression (p < 0.0001), presence of TMPRSS2:ERG fusion (p < 0.0001), and 8 of 11 chromosomal deletions (3p13, 5q21, 8p21, 10q23, 12p13, 13q14, 16q24, and 17p13; p < 0.05 each). Particularly strong associations with PTEN and 12p13 deletions (p < 0.0001 each) may indicate a functional relationship, which has already been established for PNUTS and PTEN. PNUTS had no additional role on outcome in PTEN-deleted cancers. In conclusion, the results of our study identify high PNUTS protein levels as a predictor of poor prognosis possibly linked to increased levels of genomic instability. PNUTS measurement, either alone or in combination, might be of clinical utility in prostate cancers.