Polycomb group (PcG) proteins are major determinants of gene silencing and epigenetic memory in higher eukaryotes. Here, we systematically mapped the human PcG complexome using a robust affinity purification mass spectrometry approach. Our high-density protein interaction network uncovered a diverse range of PcG complexes. Moreover, our analysis identified PcG interactors linking them to the PcG system, thus providing insight into the molecular function of PcG complexes and mechanisms of recruitment to target genes. We identified two human PRC2 complexes and two PR-DUB deubiquitination complexes, which contain the O-linked N-acetylglucosamine transferase OGT1 and several transcription factors. Finally, genome-wide profiling of PR-DUB components indicated that the human PR-DUB and PRC1 complexes bind distinct sets of target genes, suggesting differential impact on cellular processes in mammals.