The generation of genome-wide data derived from methylated DNA immunoprecipitation followed by sequencing (MeDIP-seq) has become a major tool for epigenetic studies in health and disease. The computational analysis of such data, however, still falls short on accuracy, sensitivity, and speed. We propose a time-efficient statistical method that is able to cope with the inherent complexity of MeDIP-seq data with similar performance compared with existing methods. In order to demonstrate the computational approach, we have analyzed alterations in DNA methylation during the differentiation of human embryonic stem cells (hESCs) to definitive endoderm. We show improved correlation of normalized MeDIP-seq data in comparison to available whole-genome bisulfite sequencing data, and investigated the effect of differential methylation on gene expression. Furthermore, we analyzed the interplay between DNA methylation, histone modifications, and transcription factor binding and show that in contrast to de novo methylation, demethylation is mainly associated with regions of low CpG densities.