Polycomb group (PcG) proteins exist in at least two biochemically distinct protein complexes, the EED-EZH2 complex and the PRC1 complex, that respectively possess H3-K27 methyltransferase and H2A-K119 ubiquitin E3 ligase activities. How the enzymatic activities are regulated and what their role is in Hox gene silencing are not clear. Here, we demonstrate that Bmi-1 and Ring1A, two components of the PRC1 complex, play important roles in H2A ubiquitylation and Hox gene silencing. We show that both proteins positively regulate H2A ubiquitylation. Chromatin immunoprecipitation (ChIP) assays demonstrate that Bmi-1 and other components of the two PcG complexes bind to the promoter of HoxC13. Knockout Bmi-1 results in significant loss of H2A ubiquitylation and upregulation of Hoxc13 expression, whereas EZH2-mediated H3-K27 methylation is not affected. Our results suggest that EZH2-mediated H3-K27 methylation functions upstream of PRC1 and establishes a critical role for Bmi-1 and Ring1A in H2A ubiquitylation and Hox gene silencing.