Recent comparative analyses of histone post-translational modifications (PTMs) demonstrated that the complex regulatory landscape present in bilaterians evolved before they diverged from cnidarians. However, it remains unclear if these regulatory innovations, which appear to underlie eumetazoan complexity and diversity, evolved earlier and were part of the genomic landscape of the very first crown animals. Here, using ChIP-Seq, we extend these analyses to generate genome-wide maps of regulatory elements in the sponge Amphimedon queenslandica. As a sponge, Amphimedon has one of the least complex animal body plans and is an extant representative of one of the oldest animal phyletic lineages. Despites it morphological simplicity - it lacks a gut, nerves and muscles - we show that this sponge shares a conserved gene regulatory landscape with eumetazoans (cnidarians + bilaterians). We found that Amphimedon distal cis-regulatory sites are characterized by the same combination of histone PTMs – H3K4me1 and H3K27ac – typically associated with eumetazoan enhancers and are preferentially enriched in the vicinity of developmental regulatory genes. Moreover, many of these distal cis-regulatory sites are located in microsyntenic gene blocks that are deeply conserved between sponges and eumetazoans, consistent with cis-regulation constraining genome architectures since the origin of animals. Overall, these results argue that a major shift in genome cis-regulatory complexity occurred along the metazoan stem, concomitant with the evolution of animal multicellularity. With a complex gene regulatory landscape already in place at the dawn of animals, we hypothesize that quantitative rather than qualitative differences in regulatory mechanisms led to the evolution of the diversity of eumetazoan body plans, mainly the expansion of developmental gene families (encoding transcription factors and components of signaling pathways), cis-regulatory DNA, non-coding RNAs and the subsequent enlargement and rewiring of regulatory networks.