As central players of the innate immune system, natural killer (NK) cells can exert direct and indirect anti-tumor effects via their cytotoxic and immune regulatory capacities, pivotal in the induction of an effective adaptive anti-tumor immune response. Hence, NK cells are considered to be important in the immune surveillance of cancer. In acute myeloid leukemia (AML) patients, however, significantly impaired NK cell functions can facilitate escape from immune surveillance and affect patient outcome. Here, we review various NK cell defects and AML evasion mechanisms to escape from NK cell-mediated immune surveillance and we discuss NK cell-related parameters as prediction factors of AML patient outcome. On the basis of these observations, novel immunotherapeutic strategies capitalizing on the potentiation of NK cell functions have emerged in AML immunotherapy, as discussed in this review. Increased knowledge on AML escape routes from NK cell immune surveillance will further aid in the design of novel NK cell-based immunotherapy approaches for the treatment of AML.