We have examined changes in the chromatin landscape during muscle differentiation by mapping the genome-wide location of ten key histone marks and transcription factors in mouse myoblasts and terminally differentiated myotubes, providing an exceptionally rich dataset that has enabled discovery of key epigenetic changes underlying myogenesis. Using this compendium, we focused on a well-known repressive mark, histone H3 lysine 27 trimethylation, and identified novel regulatory elements flanking the myogenin gene that function as a key differentiation-dependent switch during myogenesis. Next, we examined the role of Polycomb-mediated H3K27 methylation in gene repression by systematically ablating components of both PRC1 and PRC2 complexes. Surprisingly, we found mechanistic differences between transient and permanent repression of muscle differentiation and lineage commitment genes and observed that the loss of PRC1 and PRC2 components produced opposing differentiation defects. These phenotypes illustrate striking differences as compared to embryonic stem cell differentiation and suggest that PRC1 and PRC2 do not operate sequentially in muscle cells. Our studies of PRC1 occupancy also suggested a "fail-safe" mechanism, whereby PRC1/Bmi1 concentrates at genes specifying nonmuscle lineages, helping to retain H3K27me3 in the face of declining Ezh2-mediated methyltransferase activity in differentiated cells.