Purpose Diagnostic and prognostic tools for prostate cancer (PC) are suboptimal, causing overtreatment of indolent PC and risk of delayed treatment of aggressive PC. Here, we identify six novel candidate DNA methylation markers for PC with promising diagnostic and prognostic potential. Methods Microarray-based screening and bisulfite sequencing of 20 nonmalignant and 29 PC tissue specimens were used to identify new candidate DNA hypermethylation markers for PC. Diagnostic and prognostic potential was evaluated in 35 nonmalignant prostate tissue samples, 293 radical prostatectomy (RP) samples (cohort 1, training), and 114 malignant RP samples (cohort 2, validation) collected in Denmark, Switzerland, Germany, and Finland. Sensitivity and specificity for PC were evaluated by receiver operating characteristic analyses. Correlations between DNA methylation levels and biochemical recurrence were assessed using log-rank tests and univariate and multivariate Cox regression analyses. Results Hypermethylation of AOX1, C1orf114, GAS6, HAPLN3, KLF8, and MOB3B was highly cancer specific (area under the curve, 0.89 to 0.98). Furthermore, high C1orf114 methylation was significantly (P < .05) associated with biochemical recurrence in multivariate analysis in cohort 1 (hazard ratio [HR], 3.10; 95% CI, 1.89 to 5.09) and was successfully validated in cohort 2 (HR, 3.27; 95% CI, 1.17 to 9.12). Moreover, a significant (P < .05) three-gene prognostic methylation signature (AOX1/C1orf114/HAPLN3), classifying patients into low- and high-methylation subgroups, was trained in cohort 1 (HR, 1.91; 95% CI, 1.26 to 2.90) and validated in cohort 2 (HR, 2.33; 95% CI, 1.31 to 4.13). Conclusion We identified six novel candidate DNA methylation markers for PC. C1orf114 hypermethylation and a three-gene methylation signature were independent predictors of time to biochemical recurrence after RP in two PC patient cohorts.