KIR (killer cell immunoglobulin-like receptors) and HLA (human leukocyte antigens) are two distinct gene families with remarkable importance for human immune responses. The recognition of HLA molecules by activating and inhibitory KIR promotes a balance of signals that regulates NK cell function and is especially important for the innate defense against pathogens and early placentation. There is no documented gametic association between these two gene families and no evidence of common regulation. However, due to the critical role of KIR recognition for immunity and reproduction, the possibility of KIR-HLA combinations being under selective pressure is not surprising. In this manuscript, we first summarize the HLA-KIR system, the HLA molecules that are the putative ligands for KIR, and then we review the evidences that suggest these two gene families are coevolving as an integrated system.