Natural killer (NK) cells discriminate between normal syngeneic cells and infected, neoplastic or MHC-disparate allogeneic cells. The reactivity of NK cells appears to be regulated by a balance between activating receptors that recognize non-self or altered self, and inhibitory receptors recognizing normal, self-encoded MHC class I molecules. Subfamilies of NK receptors undergo rapid evolution, and appear to co-evolve with the MHC. We here review present views on the evolution and function of NK cell receptors, with an emphasis on knowledge gained in cattle and rodents.