Prostate cancer (PCa) a leading cause of cancer-related death in men. Prostate specific antigen (PSA) screening has reduced PCa-related mortality but at the high price of over-detection of latent disease. Furthermore, PSA is marred by an unacceptably high false-positive rate. Thus, alternative biomarkers are required. Promoter hypermethylation at specific gene loci is known to be a prevalent oncogenic event in PCa. The aim of this study was to carry out an integrative, quantitative analysis of DNA methylation to determine a highly PCa-specific panel that could be used as a molecular correlate of adverse clinicopathologic features as an adjunct to PSA to improve the early detection of PCa. We examined methylation of 9 genes (APC, CDKN2A, DCR2, GSTP1, IGFBP3, IGFBP7, PTGS2, SFRP2 and TMS1) in combination, in PCa and control groups: tumor-adjacent histologically benign tissue (TAB) and benign prostatic hyperplasia (BPH), from men with no evidence of PCa. Using a previously reported analytic method, a methylation (M) score was calculated for each sample to predict the risk of PCa in individual subjects, by summing the log odds ratio for each gene analyzed by multivariate logistic regression analysis of tumor versus benign. Two multi-gene methylation panels (M_score(APC, GSTP1, IGFBP3) and M_score(APC, GSTP1)) were identified, which differentiated between PCa and TAB (sensitivity 91.1%; specificity 80%) or PCa and BPH (sensitivity 91%; specificity 85.9%), respectively. The high tumor-specificity of the M_score warrants further investigations into liquid samples of blood and urine to determine the sensitivity of this test for non-invasive detection of PCa.