Viruses and natural killer (NK) cells have a long co-evolutionary history, evidenced by patterns of specific NK gene frequencies in those susceptible or resistant to infections. The killer immunoglobulin-like receptors (KIR) and their human leukocyte antigen (HLA) ligands together form the most polymorphic receptor-ligand partnership in the human genome and govern the process of NK cell education. The KIR and HLA genes segregate independently, thus creating an array of reactive potentials within and between the NK cell repertoires of individuals. In this review, we discuss the interplay between NK cell education and adaptation with virus infection, with a special focus on three viruses for which the NK cell response is often studied: human immunodeficiency virus (HIV), hepatitis C virus (HCV) and human cytomegalovirus (HCMV). Through this lens, we highlight the complex co-evolution of viruses and NK cells, and their impact on viral control.