The complex relationship between DNA methylation, chromatin modification, and underlying DNA sequence is often difficult to unravel with existing technologies. Here, we describe a novel technique based on high-throughput sequencing of bisulfite-treated chromatin immunoprecipitated DNA (BisChIP-seq), which can directly interrogate genetic and epigenetic processes that occur in normal and diseased cells. Unlike most previous reports based on correlative techniques, we found using direct bisulfite sequencing of Polycomb H3K27me3-enriched DNA from normal and prostate cancer cells that DNA methylation and H3K27me3-marked histones are not always mutually exclusive, but can co-occur in a genomic region-dependent manner. Notably, in cancer, the co-dependency of marks is largely redistributed with an increase of the dual repressive marks at CpG islands and transcription start sites of silent genes. In contrast, there is a loss of DNA methylation in intergenic H3K27me3-marked regions. Allele-specific methylation status derived from the BisChIP-seq data clearly showed that both methylated and unmethylated alleles can simultaneously be associated with H3K27me3 histones, highlighting that DNA methylation status in these regions is not dependent on Polycomb chromatin status. BisChIP-seq is a novel approach that can be widely applied to directly interrogate the genomic relationship between allele-specific DNA methylation, histone modification, or other important epigenetic regulators.