Promoter hypermethylation is central in deregulating gene expression in cancer. Identification of novel methylation targets in specific cancers provides a basis for their use as biomarkers of disease occurrence and progression. We developed an in silico strategy to globally identify potential targets of promoter hypermethylation in prostate cancer by screening for 5′ CpG islands in 631 genes that were reported as downregulated in prostate cancer. A virtual archive of 338 potential targets of methylation was produced. One candidate, IGFBP3, was selected for investigation, along with glutathione-S-transferase pi (GSTP1), a well-known methylation target in prostate cancer. Methylation of IGFBP3 was detected by quantitative methylation-specific PCR in 49/79 primary prostate adenocarcinoma and 7/14 adjacent preinvasive high-grade prostatic intraepithelial neoplasia, but in only 5/37 benign prostatic hyperplasia (P< 0.0001) and in 0/39 histologically normal adjacent prostate tissue, which implies that methylation of IGFBP3 may be involved in the early stages of prostate cancer development. Hypermethylation of IGFBP3 was only detected in samples that also demonstrated methylation of GSTP1 and was also correlated with Gleason score⩾ 7 (P= 0.01), indicating that it has potential as a prognostic marker. In addition, pharmacological demethylation induced strong expression of IGFBP3 in LNCaP prostate cancer cells. Our concept of a methylation candidate gene bank was successful in identifying a novel target of frequent hypermethylation in early-stage prostate cancer. Evaluation of further relevant genes could contribute towards a methylation signature of this disease.