Natural killer (NK) cells are the first lymphocyte population to reconstitute following allogeneic hematopoietic stem cell transplantation (HSCT) and are important in mediating immunity against both leukemia and pathogens. Although NK cell numbers generally reconstitute within a month, the acquisition of mature NK cell phenotype and full functional competency can take 6 months or more, and is influenced by graft composition, concurrent pharmacologic immunosuppression, graft-versus-host disease and other clinical factors. In addition, cytomegalovirus infection and reactivation have a dominant effect on NK cell memory imprinting following allogeneic HSCT just as it does in healthy individuals. Our understanding of NK cell education and licensing has evolved in the years since the ‘missing self’ hypothesis for NK-mediated graft-versus-leukemia effect was first put forward. For example, we now know that NK cell ‘re-education’ can occur, and that unlicensed NK cells can be more protective than licensed NK cells in certain settings, thus raising new questions about how best to harness graft-versus-leukemia effect. Here we review current understanding of the functional reconstitution of NK cells and NK cell education following allogeneic HSCT, highlighting a conceptual framework for future research.