RING1B, a Polycomb Group (PcG) protein, binds methylated chromatin through its association with another PcG protein called Polycomb (Pc). However, RING1B can associate with nonmethylated chromatin suggesting an alternate mechanism for RING1B interaction with chromatin. Here, we demonstrate that two proteins with little sequence identity between them, the Pc cbox domain and RYBP, bind the same surface on the C-terminal domain of RING1B (C-RING1B). Pc cbox and RYBP each fold into a nearly identical, intermolecular beta sheet with C-RING1B and a loop structure which are completely different in the two proteins. Both the beta sheet and loop are required for stable binding and transcription repression. Further, a mutation engineered to disrupt binding on the Drosophila dRING1 protein prevents chromatin association and PcG function in vivo. These results suggest that PcG targeting to different chromatin locations relies, in part, on binding partners of C-RING1B that are diverse in sequence and structure.