For over a decade, multiple studies have disputed the notion of natural killer (NK) cells as purely innate lymphocytes by demonstrating that they are capable of putative antigen-specific immunological memory against multiple infectious agents including two critical global health priorities – human immunodeficiency virus (HIV) and influenza. However, the mechanisms underlying antigen specificity remain unknown. Herein, we demonstrate that antigen-specific human NK cell memory develops upon exposure to both HIV and influenza, unified by a conserved and epitope-specific targetable mechanism largely dependent on the activating CD94/NKG2C receptor and its ligand HLA-E, and confirm these findings by three rigorous assays. We validated the permanent acquisition of antigen-specificity by individual memory NK cells by single-cell cloning. We identified biomarkers of antigen-specific NK cell memory through complex immunophenotyping by 30-parameter flow cytometry showing elevated expression of KLRG1, a4b7, and NKG2C. Finally, we show individual HLA-E-restricted peptides that may constitute the dominant NK cell response in HIV-1- and influenza-infected persons in vivo. Our findings clarify the mechanisms behind antigen-specific memory NK cell responses, and suggest they could be targeted for future vaccines, cure strategies, or other therapeutic interventions.