Cross-talk between DNA methylation and histone modifications drives the establishment of composite epigenetic signatures and is traditionally studied using correlative rather than direct approaches. Here we present sequential ChIP-bisulfite-sequencing (ChIP-BS-seq) as an approach to quantitatively assess DNA methylation patterns associated with chromatin modifications or chromatin-associated factors directly. A chromatin-immunoprecipitation (ChIP)-capturing step is used to obtain a restricted representation of the genome occupied by the epigenetic feature of interest, for which a single-base resolution DNA methylation map is then generated. When applied to H3 lysine 27 tri-methylation (H3K27me3), we found that H3K27me3 and DNA methylation are compatible throughout most of the genome, except for CpG islands, where these two marks are mutually exclusive. Further ChIP-BS-seq-based analysis in Dnmt triple-knock-out (TKO) embryonic stem cells revealed that total loss of CpG methylation is associated with alteration of H3K27me3 levels throughout the genome: H3K27me3 in localized peaks is decreased while broad local enrichments (BLOCs) of H3K27me3 are formed. At an even broader scale, these BLOCs correspond to regions of high DNA methylation in wild-type ES cells, suggesting that DNA methylation prevents H3K27me3 deposition locally and at megabase scale. Our strategy provides an unique way of investigating global interdependencies between DNA methylation and other chromatin features.