Vertebrates have highly methylated genomes at CpG positions while most invertebrates have sparsely methylated genomes. Therefore, hypermethylation is considered a major innovation that shaped the genome and the regulatory roles of DNA methylation in vertebrates. However, here we report that the marine sponge Amphimedon queenslandica, belonging to one of the earliest branching animal lineages, has evolved a hypermethylated genome with remarkable similarities to that of a vertebrate. Despite major differences in genome size and architecture, independent acquisition of hypermethylation reveal common distribution patterns and repercussions for genome regulation between both lineages. Genome wide depletion of CpGs is counterbalanced by CpG enrichment at unmethylated promoters, mirroring CpG islands. Furthermore, a subset of CpG-bearing transcription factor motifs are enriched at Amphimedon unmethylated promoters. We find that the animal-specific transcription factor NRF has conserved methyl-sensitivity over 700 million years, indicating an ancient cross-talk between transcription factors and DNA methylation. Finally, the sponge shows vertebrate-like levels of 5-hydroxymethylcytosine, the oxidative derivative of cytosine methylation involved in active demethylation. Hydroxymethylation is concentrated in regions that are enriched for transcription factor motifs and show developmentally dynamic demethylation. Together, these findings push back the links between DNA methylation and its regulatory roles to the early steps of animal evolution. Thus, the Amphimedon methylome challenges the prior hypotheses about the origins of vertebrate genome hypermethylation and its implications for regulatory complexity. Overall design: Profiling of cytosine methylation for Amphimedon queenslandica, Sycon ciliatum, Mnemiopsis leidyi and Nematostella vectensis. Profiling hydroxymethylation with TAB-seq for Amphimedon queenslandica and Nematostella vectensis. DAP-seq and ampDAP-seq for Amphimedon transcription factors on Amphimedon queenslandica genomic DNA.