The TMPRSS2-ERG gene fusion is one of the most frequent gene rearrangements found in about 50% of human prostate tumors. However, uncertainty persists regarding the molecular determinants of ERG-induced oncogenesis and its role in tumor progression. We report a novel molecular interaction between ERG and the H3K27 histone methyltransferase EZH2. We found that ERG possesses a H3K27-like motif (RKS) centered at lysine 362 (K362), and that EZH2 was able to catalyze its methylation. K362 methylation, and interaction with EZH2, enhanced both trans-activation and trans-repression mediated by ERG and contributed to global transcriptional and phenotypic reprograming in ERG positive tumors. ERG and EZH2 co-localized in several regions of the genome of ERG positive prostate cancer cells, and most of these co-occupied genes constituted a set of highly deregulated genes in primary and metastatic ERG positive tumors. Notably, PTEN loss, which is frequently observed in prostate tumors with ERG fusion, and is associated with adverse prognosis, promoted ERG methylation. This study gives new insights providing a broadly relevant mechanism for tumor progression, and defines a therapeutically actionable pathway for the management of ERG positive prostate cancers.