The Animal Kingdom shows an astonishing diversity, the product of over 550 million years of animal evolution. The current wealth of genome sequence data offers an opportunity to better understand the genomic basis of this disparity. Here we analyse a sampling of 102 whole genomes including >2.6 million protein sequences. We infer major genomic patterns associated with the variety of animal forms from superphylum to phylum level. We show a remarkable amount of gene loss that occurred during the evolution of two major groups of bilaterian animals, Ecdysozoa and Deuterostomia, and further loss in several deuterostome lineages. Deuterostomes and Protostomes also show large genome novelties. At the phylum level flatworms, nematodes and tardigrades show the largest reduction of gene complement, alongside gene novelty. These findings paint a picture of the evolution within the Animal Kingdom in which reductive evolution at protein-coding level played a major role in shaping genome composition.