Natural killer (NK) cells are bone marrow–derived granular lymphocytes that have a key role in immune defense against viral and bacterial infections and malignancies. NK cells are traditionally defined as cells of the innate immune response because they lack RAG recombinase–dependent clonal antigen receptors. However, evidence suggests that specific subsets of mouse NK cells can nevertheless develop long-lived and highly specific memory to a variety of antigens. Here we review published evidence of NK cell–mediated, RAG-independent adaptive immunity. We also compare and contrast candidate mechanisms for mammalian NK cell memory and antigen recognition with other examples of RAG-independent pathways that generate antigen receptor diversity in non-mammalian species and discuss NK cell memory in the context of lymphocyte evolution.