Immunological memory has traditionally been regarded as a unique feature of the adaptive immune response, mediated in an antigen-specific manner by T and B lymphocytes. All other hematopoietic cells, including natural killer (NK) cells, are classified as innate immune cells, which have been considered short-lived but can respond rapidly against pathogens in a manner not thought to be driven by antigen. Interestingly, NK cells have recently been shown to survive long term after antigen exposure and subsequently mediate antigen-specific recall responses. In this review, we address the similarities between, and the controversies surrounding, three major viewpoints of NK memory that have arisen from these recent studies: (i) mouse cytomegalovirus (MCMV)-induced memory; (ii) cytokine-induced memory; and (iii) liver-restricted memory cells.