Ring1B/Rnf2 is a RING finger protein member of the Polycomb group (PcG) of proteins, which form chromatin-modifying complexes essential for embryonic development and stem cell renewal and which are commonly deregulated in cancer. Ring1B/Rnf2 is a ubiquitin E3 ligase that catalyzes the monoubiquitylation of the histone H2A, one of the histone modifications needed for the transcriptional repression activity of the PcG of proteins. Ring1B/Rnf2 was shown to be part of two complexes, the PRC1 PcG complex and the E2F6.com-1 complex, which also contains non-PcG members, thus raising the prospect for additional Ring1B/Rnf2 partners and functions extending beyond the PcG. Here we used a high throughput proteomics approach based on the single step purification, using streptavidin beads, of in vivo biotinylated Ring1B/Rnf2 and associated proteins from a nuclear extract from erythroid cells and their identification by mass spectrometry. About 50 proteins were confidently identified of which 20 had not been identified previously as subunits of Ring1B/Rnf2 complexes. We found that histone demethylases LSD1/Aof2 and Fbxl10/Jhdm1B, casein kinase subunits, and the BcoR corepressor were among the new interactors identified. We also isolated an Fbxl10/Jhdm1B complex by biotinylation tagging to identify shared interacting partners with Ring1B/Rnf2. In this way we identified a novel Ring1B-Fbxl10 complex that also includes Bcl6 corepressor (BcoR), CK2alpha, Skp1, and Nspc1/Pcgf1. The putative enzymatic activities and protein interaction and chromatin binding motifs present in this novel Ring1B-Fbxl10 complex potentially provide additional mechanisms for chromatin modification/recruitment to chromatin and more evidence for Ring1B/Rnf2 activities beyond those typically associated with PcG function. Lastly this work demonstrates the utility of biotinylation tagging for the rapid characterization of complex mixtures of multiprotein complexes achieved through the iterative use of this simple yet high throughput proteomics approach.