Skeletal muscle cell differentiation (myogenesis) is a process orchestrated by a complex network involving transcription factors, epigenetic regulators, and microRNAs. Previous studies identified miR-29 as a pro-myogenic factor that interacts with components of Polycomb repressive complex, YY1 and Ezh2. In a genome-wide survey of miR-29-mediated transcriptome changes in C2C12 myoblasts, many epigenetic factors were found to be down-regulated by miR-29. Among them, Rybp was shown to be a direct target of miR-29 through binding to its 3' UTR. Functional studies demonstrated that Rybp is down-regulated during myogenesis and acts as a negative regulator of skeletal myogenesis both in vitro during C2C12 differentiation and in vivo in injury-induced muscle regeneration. Furthermore, we found that Rybp and YY1 co-occupy several myogenic loci, including miR-29 itself, to silence their expression, thus forming a Rybp-miR-29 feedback loop. Rybp overexpression was found to enhance the enrichment of Ezh2 and trimethylation of H3K27 at target loci, suggesting it may facilitate the recruitment or stabilization of the Polycomb repressive complex. Collectively, our results identify Rybp as a novel regulator of myogenesis that co-acts with YY1 to silence miR-29 and other myogenic loci.