Methylation of cytosines is the prototypic epigenetic modification of the DNA. It has been implicated in various regulatory mechanisms throughout the animal kingdom and particularly in vertebrates. We mapped DNA methylation in 580 animal species (535 vertebrates, 45 invertebrates), resulting in 2443 genome-scale, base-resolution DNA methylation profiles of primary tissue samples from various or-gans. Reference-genome independent analysis of this comprehensive dataset quantified the association of DNA methylation with the underlying genomic DNA sequence throughout vertebrate evolution. We observed a broadly conserved link with two major transitions – once in the first vertebrates and again with the emergence of reptiles. Cross-species comparisons focusing on individual organs supported a highly conserved role of DNA methylation in defining tissue types, and cross-mapping analysis of DNA methylation at gene promoters revealed evolutionary changes for specific genes. In summary, this study establishes a large resource of vertebrate and invertebrate DNA methylomes, it showcases the power of reference-free epigenome analysis in species for which no reference genomes are availa-ble, and it contributes an epigenetic perspective to the study of vertebrate evolution.