This study aimed to validate whether 5-hydroxymethylcytosine (5hmC) level in combination with ERG expression is a predictive biomarker for biochemical failure (BF) in men undergoing radical prostatectomy (RP) for prostate cancer (PCa). The study included 592 PCa patients from two consecutive Danish RP cohorts. 5hmC level and ERG expression were analyzed using immunohistochemistry in RP specimens. 5hmC was scored as low or high and ERG was scored as negative or positive. Risk of BF was analyzed using stratified cumulative incidences and multiple cause-specific Cox regression using competing risk assessment. Median follow-up was 10 years (95% CI: 9.5–10.2). In total, 246 patients (41.6%) had low and 346 patients (58.4%) had high 5hmC level. No significant association was found between 5hmC level or ERG expression and time to BF (p = 0.2 and p = 1.0, respectively). However, for men with ERG negative tumors, high 5hmC level was associated with increased risk of BF following RP (p = 0.01). In multiple cause-specific Cox regression analyses of ERG negative patients, high 5hmC expression was associated with time to BF (HR: 1.8; 95% CI: 1.2–2.7; p = 0.003). In conclusion, high 5hmC level was correlated with time to BF in men with ERG negative PCa, which is in accordance with previous results.