Abstract Background Prostate cancer (PC) can be stratified into distinct molecular subtypes based on TMPRSS2-ERG gene fusion status, but its potential prognostic value remains controversial. Likewise, routine clinicopathological features cannot clearly distinguish aggressive from indolent tumors at the time of diagnosis; thus, new prognostic biomarkers are urgently needed. The DNA methylation variant 5-hydroxymethylcytosine (5hmC, an oxidized derivative of 5-methylcytosine) has recently emerged as a new diagnostic and/or prognostic biomarker candidate for several human malignancies. However, this remains to be systematically investigated for PC. In this study, we determined 5hmC levels in 311 PC (stratified by ERG status) and 228 adjacent non-malignant (NM) prostate tissue specimens by immunohistochemical analysis of a tissue microarray, representing a large radical prostatectomy (RP) cohort with long clinical follow-up. We investigated possible correlations between 5hmC and routine clinicopathological variables and assessed the prognostic potential of 5hmC by Kaplan-Meier and uni- and multivariate Cox regression analyses in ERG+ ( n  = 178) vs . ERG− ( n  = 133) PCs using biochemical recurrence (BCR) as endpoint. Results We observed a borderline significant ( p  = 0.06) reduction in 5hmC levels in PC compared to NM tissue samples, which was explained by a highly significant ( p