Natural killer (NK) cells are a population of cytotoxic innate lymphocytes that evolved prior to their adaptive counterparts and constitute one of the first lines of defense against infected/mutated cells. Several studies have shown that in patients with acute leukemia given haploidentical hematopoietic stem cell transplantation, donor-derived NK cells play a key role in the eradication of cancer cells. The antileukemic effect is mostly related to the presence of “alloreactive” NK cells, that is, mature KIR+ NK cells that express inhibitory KIR mismatched with HLA class I (KIR-L) of the patient. A genotypic analysis detecting KIR B haplotype and the relative B content is an additional donor selection criterion. These data provided the rationale for implementing phase I/II clinical trials of adoptive infusion of either selected or ex vivo-activated NK cells, often from an HLA-mismatched donor. In this review, we provide a historical perspective on the role played by NK cells in patients with acute leukemia, focusing also on the various approaches to adoptive NK cell therapy and the unresolved issues therein. In addition, we outline new methods to enhance NK activity, including anti-KIR monoclonal antibody, bi-/trispecific antibodies linking NK cells to cytokines and/or target antigens, and CAR-engineered NK cells.