The Polycomb Group (PcG) protein EZH2 is a critical component of a multiprotein complex that methylates Lys²⁷ of histone 3 (H3K27), which consequently leads to the repression of target gene expression. We have previously reported that EZH2 is overexpressed in metastatic prostate cancer and is a marker of aggressive diseases in clinically localized solid tumors. However, the global set of genes directly regulated by PcG in tumors is largely unknown, and thus how PcG mediates tumor progression remains unclear. Herein we mapped genome-wide H3K27 methylation in aggressive, disseminated human prostate cancer tissues. Integrative analysis revealed that a significant subset of these genes are also targets of PcG in embryonic stem cells, and their repression in tumors is associated with poor prognosis. By stepwise cross-validation, we developed a “Polycomb repression signature” composed of 14 direct targets of PcG in metastatic tumors. Notably, solid tumor subtypes in which this gene signature is repressed show poor clinical outcome in multiple microarray data sets of tumors including breast and prostate cancer. Taken together, our results show a fingerprint of PcG-mediated transcriptional repression in metastatic prostate cancer that is reminiscent of stem cells and associated with cancer progression. Therefore, PcG proteins play a central role in the epigenetic silencing of target genes and functionally link stem cells, metastasis, and cancer survival. [Cancer Res 2007;67(22):10657–63]