Aberrant DNA methylation patterns may be the earliest somatic genome changes in prostate cancer. Using real-time methylation-specific PCR, we assessed the extent of hypermethylation at 16 CpG islands in DNA from seven prostate cancer cell lines (LNCaP, PC-3, DU-145, LAPC-4, CWR22Rv1, VCaP, and C42B), normal prostate epithelial cells, normal prostate stromal cells, 73 primary prostate cancers, 91 metastatic prostate cancers, and 25 noncancerous prostate tissues. We found that CpG islands at GSTP1, APC, RASSF1a, PTGS2, and MDR1 were hypermethylated in >85% of prostate cancers and cancer cell lines but not in normal prostate cells and tissues; CpG islands at EDNRB, ESR1, CDKN2a, and hMLH1 exhibited low to moderate rates of hypermethylation in prostate cancer tissues and cancer cell lines but were entirely unmethylated in normal tissues; and CpG islands at DAPK1, TIMP3, MGMT, CDKN2b, p14/ARF, and CDH1 were not abnormally hypermethylated in prostate cancers. Receiver operator characteristic curve analyses suggested that CpG island hypermethylation changes at GSTP1, APC, RASSF1a, PTGS2, and MDR1 in various combinations can distinguish primary prostate cancer from benign prostate tissues with sensitivities of 97.3–100% and specificities of 92–100%. Hypermethylation of the CpG island at EDNRB was correlated with the grade and stage of the primary prostate cancers. PTGS2 CpG island hypermethylation portended an increased risk of recurrence. Furthermore, CpG island hypermethylation patterns in prostate cancer metastases were very similar to the primary prostate cancers and tended to show greater differences between cases than between anatomical sites of metastasis.