The mechanisms by which the major Polycomb group (PcG) complexes PRC1 and PRC2 are recruited to target sites in vertebrate cells are not well understood. Building on recent studies that determined a reciprocal relationship between DNA methylation and Polycomb activity, we demonstrate that, in methylation-deficient embryonic stem cells (ESCs), CpG density combined with antagonistic effects of H3K9me3 and H3K36me3 redirects PcG complexes to pericentric heterochromatin and gene-rich domains. Surprisingly, we find that PRC1-linked H2A monoubiquitylation is sufficient to recruit PRC2 to chromatin in vivo, suggesting a mechanism through which recognition of unmethylated CpG determines the localization of both PRC1 and PRC2 at canonical and atypical target sites. We discuss our data in light of emerging evidence suggesting that PcG recruitment is a default state at licensed chromatin sites, mediated by interplay between CpG hypomethylation and counteracting H3 tail modifications.