Methylation at the 5 position of cytosine in DNA (5meC) is a key epigenetic mark in eukaryotes. Once introduced, 5meC can be maintained through DNA replication by the activity of 'maintenance' DNA methyltransferases (DNMTs). Despite their ancient origin, DNA methylation pathways differ widely across animals, such that 5meC is either confined to transcribed genes or lost altogether in several lineages. We used comparative epigenomics to investigate the evolution of DNA methylation. Although the model nematode Caenorhabditis elegans lacks DNA methylation, more basal nematodes retain cytosine DNA methylation, which is targeted to repeat loci. We found that DNA methylation coevolved with the DNA alkylation repair enzyme ALKB2 across eukaryotes. In addition, we found that DNMTs introduced the toxic lesion 3-methylcytosine into DNA both in vitro and in vivo. Alkylation damage is therefore intrinsically associated with DNMT activity, and this may promote the loss of DNA methylation in many species.