The past fifteen years have witnessed great progress in our undestanding of how natural killer (NK) cells function, their role in innate defenses and their possible exploitation in therapy. This contribution traces the major advances in these formerly mysterious cells, from the first discovery of HLA-class I-specific inhibitory receptors to a more recent major breakgthrough that highlighted important perspectives and major expectations regarding the cure of life-threatening leukemias. The key role of "alloreactive" NK cells in eradicating acute myeloid leukemias and in preventing both graft rejection and graft-versus-host disease, led to a true revolution in bone marrow transplantation. Thus, it is now possible to search for appropriate HLA class I mismatches to set NK cells in action to cure high risk leukemias.