Immunological memory is a hallmark of the adaptive immune system. However, the ability to remember and respond more robustly against a second encounter with the same pathogen has been described in organisms lacking T and B cells. Recently, NK cells have been shown to mediate Ag-specific recall responses in several different model systems. Although NK cells do not rearrange the genes encoding their activating receptors, NK cells experience a selective education process during development, undergo a clonal-like expansion during virus infection, generate long-lived progeny (ie, memory cells), and mediate more efficacious secondary responses against previously encountered pathogens—all characteristics previously ascribed only to T and B cells in mammals. This review describes past findings leading up to these new discoveries, summarizes the evidence for and characteristics of NK cell memory, and discusses the attempts and future challenges to identify these long-lived memory NK cell populations in humans.