NKp30 is a Natural Cytotoxicity Receptor (NCR) expressed by Natural Killer (NK) cells and other lymphocytes. NKp30 is the only evolutionarily conserved NCR found in all jawed vertebrates and it coevolves with its ligand B7-H6. Using sharks as a model, we found NKp30 gene expression in subsets of mature and immature T cells, suggesting that T cells and NK cells share common features in these primitive vertebrates. To understand NKp30’s evolutionary origin, we examined genomic regions containing NKp30 and its homologs in vertebrates in different Classes. We observed that loci in paralogous regions containing NKp30 homologs are well conserved, suggesting the presence of NKp30 ancestors and other linked immune genes before the emergence of vertebrates 550 million years ago. Indeed, the corresponding region is also present in invertebrates. We hypothesize that this genomic region encompassed the “Primordial Immune Complex,” containing genes playing roles in immunity at the origin of vertebrates.