A fundamental initiative for evolutionary biologists is to understand the molecular basis underlying phenotypic diversity. A long-standing hypothesis states that species-specific traits may be explained by differences in gene regulation rather than differences at the protein level. Over the past few years, evolutionary studies have shifted from mere sequence comparisons to integrative analyses in which gene regulation is key to understanding species evolution. DNA methylation is an important epigenetic modification involved in the regulation of numerous biological processes. Nevertheless, the evolution of the human methylome and the processes driving such changes are poorly understood. Here, we review the close interplay between Cytosine-phosphate-Guanine (CpG) methylation and the underlying genome sequence, as well as its evolutionary impact. We also summarize the latest advances in the field, revisiting the main literature on human and nonhuman primates. We hope to encourage the scientific community to address the many challenges posed by the field of comparative epigenomics.