The correlation between DNA methylation and a subset of histone post-translational modifications (positive and negative) has hinted at an underlying regulatory crosstalk between histone marks and DNA methylation in patterning the human DNA methylome, an idea further supported by corresponding alterations to both histone marks and DNA methylation during malignant transformation. This study investigated the framework by which histone marks influence DNA methylation at a genome-wide level. Using RNAi in a pluripotent human embryonic carcinoma cell line we depleted essential components of the MLL/COMPASS, polycomb repressive complex 2 (PRC2), and PRC1 histone modifying complexes that establish, respectively, the post-translational modifications H3K4me3, H3K27me3, and H2AK119ub, and assayed the impact of the subsequent depletion of these marks on the DNA methylome. Absence of H2AK119ub resulted predominantly in hypomethylation across the genome. Depletion of H3K4me3 and, surprisingly, H3K27me3 caused CpG island hypermethylation at a subset of loci. Intriguingly, many promoters were co-regulated by all three histone marks, becoming hypermethylated with loss of H3K4me3 or H3K27me3 and hypomethylated with depletion of H2AK119ub, and many of these co-regulated loci were among those commonly targeted for aberrant hypermethylation in cancer. Taken together, our results elucidate novel roles for polycomb and MLL/COMPASS in regulating DNA methylation and define targets of this regulation.