Enhancer of zeste homolog 2 (EZH2) plays an important role in tumor development and progression by interacting with histone and nonhistone proteins. In the current study, we analyzed prevalence and prognostic impact of EZH2 in prostate cancer. EZH2 expression was analyzed by immunohistochemistry on a tissue microarray containing more than 12400 prostate cancer specimens. Results were compared to tumor phenotype, biochemical recurrence and molecular subtypes defined by ERG status as well as genomic deletions of 3p, 5q, 6q and PTEN. EZH2 immunostaining was detectable in 56.6% of 10168 interpretable cancers and considered strong in 1.1%, moderate in 12.2% and weak in 43.3% of cases. High EZH2 expression was strongly associated with high Gleason grade (P < 0.0001), advanced pathological tumor stage (P < 0.0001), positive nodal status (P < 0.0001), elevated preoperative PSA level (P = 0.0066), early PSA recurrence (P < 0.0001) and increased cell proliferation P < 0.0001). High-level EZH2 staining was also associated with TMPRSS2:ERG rearrangement and ERG expression in prostate cancers (P < 0.0001) and was linked to deletions of PTEN, 6q15, 5q21 and 3p13 (P < 0.0001 each) particularly in ERG-negative cancers. The prognostic impact of EZH2 was independent of established pre- and postoperatively assessed clinicopathological parameters. EZH2 has strong prognostic impact in prostate cancer and might contribute to the development of a fraction of genetically instable and particularly aggressive prostate cancers. EZH2 analysis might therefore be of clinical value for risk stratification of prostate cancer.