Epigenetic silencing in cancer cells is mediated by at least two distinct histone modifications, polycomb-based histone H3 lysine 27 trimethylation (H3K27triM) and H3K9 dimethylation. The relationship between DNA hypermethylation and these histone modifications is not completely understood. Using chromatin immunoprecipitation microarrays (ChIP-chip) in prostate cancer cells compared to normal prostate, we found that up to 5% of promoters (16% CpG islands and 84% non-CpG islands) were enriched with H3K27triM. These genes were silenced specifically in prostate cancer, and those CpG islands affected showed low levels of DNA methylation. Downregulation of the EZH2 histone methyltransferase restored expression of the H3K27triM target genes alone or in synergy with histone deacetylase inhibition, without affecting promoter DNA methylation, and with no effect on the expression of genes silenced by DNA hypermethylation. These data establish EZH2-mediated H3K27triM as a mechanism of tumor-suppressor gene silencing in cancer that is potentially independent of promoter DNA methylation.