Although the ability to discriminate self from nonself is a highly conserved animal trait, the systems enabling animal allorecognition vary markedly between taxa, suggesting independent evolutionary origins. The disparity between extant recognition systems means that understanding of the evolutionary processes shaping their underlying genes is limited. Here we explore an allorecognition gene family across an entire animal phylum, the sponges. A peculiarity of sponge physiology allows dissociated, histocompatible cells to sort into aggregates, and later, functional sponges. This process is mediated by aggregation factors (AFs), proteoglycans which have also been implicated in the sponge immune response to tissue contact, but which have not been analysed at a genomic level. We show that the demosponge Amphimedon queenslandica genome has six tightly-clustered AF genes, which encode proteins containing multiple Calx-beta and von Willebrand domains and a newly-defined Wreath domain. Despite these genes having remarkably similar exon, intron phase, and domain structures, high nucleotide and amino acid polymorphism exists between individuals, and appears to be introduced both by genomically-encoded variants and, in at least one AF gene, extensive single-nucleotide RNA editing of up to 5% of surveyed nucleotide positions. Analysis of 24 sponge genomes and transcriptomes spanning all four poriferan classes reveals that all surveyed demosponges possess AFs with Wreath domains and other similar domains to Amphimedon AFs. However, no two demosponges share matching AF gene repertoires. Representatives of other sponge classes completely lack recognisable AFs and Wreath domains. These results are consistent with the AF gene family originating at the base of the demosponges and undergoing rapid evolution via domain shuffling, recruitment and loss, resulting in the range of AFs present in modern demosponges. The continual evolution of AFs in sponges provides an explanation as to how other allorecognition genes present in the animal kingdom obtain their unique structure and organisation.