Polycomb group proteins Ring1b and Bmi1 (B-cell-specific Moloney murine leukaemia virus integration site 1) are critical components of the chromatin modulating PRC1 complex. Histone H2A ubiquitination by the PRC1 complex strongly depends on the Ring1b protein. Here we show that the E3-ligase activity of Ring1b on histone H2A is enhanced by Bmi1 in vitro. The N-terminal Ring-domains are sufficient for this activity and Ring1a can replace Ring1b. E2 enzymes UbcH5a, b, c or UbcH6 support this activity with varying processivity and selectivity. All four E2s promote autoubiquitination of Ring1b without affecting E3-ligase activity. We solved the crystal structure of the Ring-Ring heterodimeric complex of Ring1b and Bmi1. In the structure the arrangement of the Ring-domains is similar to another H2A E3 ligase, the BRCA1/BARD1 complex, but complex formation depends on an N-terminal arm of Ring1b that embraces the Bmi1 Ring-domain. Mutation of a critical residue in the E2/E3 interface shows that catalytic activity resides in Ring1b and not in Bmi1. These data provide a foundation for understanding the critical enzymatic activity at the core of the PRC1 polycomb complex, which is implicated in stem cell maintenance and cancer.