Immune memory has traditionally been the domain of the adaptive immune system, present only in antigen-specific T and B cells. The purpose of this review is to summarize the evidence for immunological memory in lower organisms (which are not thought to possess adaptive immunity) and within specific cell subsets of the innate immune system. A special focus will be given to recent findings in both mouse and humans for specificity and memory in natural killer (NK) cells, which have resided under the umbrella of innate immunity for decades. The surprising longevity and enhanced responses of previously primed NK cells will be discussed in the context of several immunization settings.