Natural killer (NK) cells affect a form of innate immunity that recognizes and eliminates cells that are infected with certain viruses or have undergone malignant transformation. In mammals, this recognition can be mediated through immunoglobulin- (Ig) and/or lectin-type NK receptors (NKRs). NKR genes in mammals range from minimally polymorphic single-copy genes to complex multigene families that exhibit high levels of haplotypic complexity and exhibit significant interspecific variation. Certain single-copy NKR genes that are present in one mammal are present as expanded multigene families in other mammals. These observations highlight NKRs as one of the most rapidly evolving eukaryotic gene families and likely reflect the influence of pathogens, especially viruses, on their evolution. Although well characterized in human and mice, cytotoxic cells that are functionally similar to NK cells have been identified in species ranging from birds to reptiles, amphibians and fish. Although numerous receptors have been identified in non-mammalian vertebrates that share structural relationships with mammalian NKRs, functionally defining these lower vertebrate molecules as NKRs is confounded by methodological and interpretive complexities. Nevertheless, several lines of evidence suggest that NK-type function or its equivalent has sustained a long evolutionary history throughout vertebrate species.