Polycomb proteins are critical chromatin modifiers that regulate stem cell differentiation via transcriptional repression. In skeletal muscle progenitors Enhancer of zeste homologue 2 (EZH2), the catalytic subunit of Polycomb Repressive Complex 2 (PRC2), contributes to maintain the chromatin of muscle genes in a repressive conformation, whereas its down-regulation allows the progression through the myogenic programme. Here, we show that p38α kinase promotes EZH2 degradation in differentiating muscle cells through phosphorylation of threonine 372. Biochemical and genetic evidence demonstrates that the MYOD-induced E3 ubiquitin ligase Praja1 (PJA1) is involved in regulating EZH2 levels upon p38α activation. EZH2 premature degradation in proliferating myoblasts is prevented by low levels of PJA1, its cytoplasmic localization and the lower activity towards unphosphorylated EZH2. Our results indicate that signal-dependent degradation of EZH2 is a prerequisite for satellite cells differentiation and identify PJA1 as a new player in the epigenetic control of muscle gene expression.