EZH2 is part of the PRC2 polycomb repressive complex that is overexpressed in multiple cancer types and has been implicated in prostate cancer initiation and progression. Here, we identify EZH2 as a target of the MYC oncogene in prostate cancer and show that MYC coordinately regulates EZH2 through transcriptional and post-transcriptional means. Although prior studies in prostate cancer have revealed a number of possible mechanisms of EZH2 upregulation, these changes cannot account for the overexpression EZH2 in many primary prostate cancers, nor in most cases of high grade PIN. We report that upregulation of Myc in the mouse prostate results in overexpression of EZH2 mRNA and protein which coincides with reductions in miR-26a and miR-26b, known regulators of EZH2 in some non-prostate cell types, albeit not in others. Further, in human prostate cancer cells, Myc negatively regulates miR-26a and miR-26b via direct binding to their parental Pol II gene promoters, and forced overexpression of miR-26a and miR-26b in prostate cancer cells results in decreased EZH2 levels and suppressed proliferation. In human clinical samples, miR-26a and miR-26b are downregulated in most primary prostate cancers. As a separate mechanism of EZH2 mRNA upregulation, we find that Myc binds directly to and activates the transcription of the EZH2 promoter. These results link two major pathways in prostate cancer by providing two additional and complementary Myc-regulated mechanisms by which EZH2 upregulation occurs and is enforced during prostatic carcinogenesis. Further, the results implicate EZH2-driven mechanisms by which Myc may stimulate prostate tumor initiation and disease progression.