The discovery of novel immune receptors has led to a recent renaissance of research into the innate immune system, following decades of intense research of the adaptive immune system. Of particular interest has been the discovery of the natural killer (NK) cell receptors which, depending on type, interact with classical or non-classical MHC class I antigens of the adaptive immune system, thus functioning at the interface of innate and adaptive immunity. Here, we review recent progress with respect to two such families of NK receptors, the killer immunoglobulin-like receptors (KIRs) and the killer cell lectin-like receptors (KLRs), and attempt to trace their evolution across vertebrates.