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.