In an adaptive immune response, naïve T cells proliferate during infection and generate long-lived memory cells that undergo secondary expansion following re-encounter with the same pathogen. Although Natural Killer cells traditionally have been classified as cells of the innate immune system, they share many similarities with cytotoxic T lymphocytes. In a mouse model of cytomegalovirus (MCMV) infection, we demonstrate that, like T cells, NK cells bearing the virus-specific Ly49H receptor proliferate 100-fold in the spleen and 1000-fold in the liver following infection. Following a contraction phase, Ly49H + NK cells reside in lymphoid and non-lymphoid organs for several months. These self-renewing “memory” NK cells rapidly degranulate and produce cytokines upon reactivation. Adoptive transfer of these NK cells into naïve animals followed by viral challenge results in a robust secondary expansion and protective immunity. These findings reveal novel properties of NK cells previously attributed only to cells of the adaptive immune system.