Colonial marine invertebrates are capable of allorecognition—the ability to discriminate between their own tissues and those of conspecifics. In the cnidarian Hydractinia symbiolongicarpus, allorecognition is controlled by a single genomic region called the Allorecognition Complex (ARC), which contains at least two allorecognition genes, Allorecognition 1 (Alr1), and Allorecognition 2 (Alr2). Both encode type I transmembrane proteins with highly polymorphic extracellular domains and are capable of homophilic binding between opposing cell membranes. In Alr2, as few as six amino acid differences in the first extracellular domain are sufficient to prevent binding between otherwise identical isoforms. Here, we used ancestral sequence reconstruction and in vitro binding assays to determine how novel binding specificities evolved within a family of closely related Alr2 alleles. Our results reveal two trajectories for the generation of a new binding specificity. In one trajectory, one amino acid change is sufficient to create a new isoform that can bind to itself but no longer binds to the ancestral isoform. In the second trajectory, four mutations ultimately lead to an allelic isoform with a novel binding specificity, but the path includes “promiscuous” intermediates that can bind to the ancestral and final isoforms. These results demonstrate it is possible to generate new functional isoforms of allorecognition proteins via relatively few mutations and have important implications for our understanding of how diversity is generated in this and other allorecognition systems.