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 organs. Reference-genome independent analysis of this comprehensive dataset defined a “genomic code” of DNA methylation, which allowed us to predict global and locus-specific DNA methylation from the DNA sequence within and across species. This code appears broadly conserved throughout vertebrate evolution, with two major transitions – once in the first vertebrates and again with the emergence of reptiles. Beyond the central role of species-specific DNA sequence composition, our dataset identified the tissue type and the individual as two main sources of DNA methylation variability within species. Tissue type was the dominant factor in fish, birds, and mammals, while in invertebrates, reptiles, and amphibians both factors were similarly strong. Cross-species comparisons focusing on heart and liver tissues supported a highly conserved role of DNA methylation for tissue type and identity and cross-mapping based promoter methylation analysis revealed divergence at 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 available, and it contributes an epigenetic perspective to the study of vertebrate evolution. Overall design: Dataset comprises 2443 DNA methylation profiles (RRBS) covering 580 animal species (535 vertebrates and 45 invertebrates) and more than 10 major tissue types with a foucs on heart and liver, analysed in a reference-free manner.