Pluripotency is accompanied by the erasure of parental epigenetic memory, with naïve pluripotent cells exhibiting global DNA hypomethylation both in vitro and in vivo. Exit from pluripotency and priming for differentiation into somatic lineages is associated with genome-wide de novo DNA methylation. We show that during this phase, co-expression of enzymes required for DNA methylation turnover, DNMT3s and TETs, promotes cell-to-cell variability in this epigenetic mark. Using a combination of single-cell sequencing and quantitative biophysical modeling, we show that this variability is associated with coherent, genome-scale oscillations in DNA methylation with an amplitude dependent on CpG density. Analysis of parallel single-cell transcriptional and epigenetic profiling provides evidence for oscillatory dynamics both in vitro and in vivo. These observations provide insights into the emergence of epigenetic heterogeneity during early embryo development, indicating that dynamic changes in DNA methylation might influence early cell fate decisions.