Natural killer (NK) cells protect against infections through a distinctive combination of innate and adaptive immune capabilities. They exhibit characteristics of immunological memory by enhanced secondary response to pathogen exposure. We discuss current progress in identifying long-lived NK cell clones with enhanced memory functionality and the capacity for intensive cytokine and cytotoxic granule production upon re-encountering external antigens. We examine data related to how various NK cell receptors facilitate the recognition of specific foreign peptides in particular human leukocyte antigen (HLA) contexts and may promote the formation of memory clones. Finally, we propose and substantiate a model that resolves the accumulated fundamental contradictions and explains the semi-antigen-specific nature of the NK cell response through the clonally imprinted expression patterns of enzymes involved in the post-translational modification of HLA-binding receptors.