Natural killer (NK) cells are large granular lymphocytes involved in our defense against certain virus-infected and malignant cells. In contrast to T cells, NK cells elicit rapid anti-tumor responses based on signals from activating and inhibitory cell surface receptors. They also lyse target cells via antibody-dependent cellular cytotoxicity, a critical mode of action of several therapeutic antibodies used to treat cancer. A body of evidence shows that NK cells can exhibit potent anti-tumor activity against chronic myeloid leukemia (CML), acute myeloid leukemia (AML), and myelodysplastic syndromes (MDS). However, disease-associated mechanisms often restrain the proper functions of endogenous NK cells, leading to inadequate tumor control and risk for disease progression. Although allogeneic NK cells can prevent leukemia relapse in certain settings of stem cell transplantation, not all patients are eligible for this type of therapy. Moreover, remissions induced by adoptively infused NK cells are only transient and require subsequent therapy to maintain durable responses. Hence, new strategies are needed to trigger full and durable anti-leukemia responses by NK cells in patients with myeloid malignancies. To achieve this, we need to better understand the interplay between the malignant cells, their microenvironment, and the NK cells. This review focuses on mechanisms that are involved in suppressing NK cells in patients with myeloid leukemia and MDS, and means to restore their full anti-tumor potential. It also discusses novel molecular targets and approaches, such as bi- and tri-specific antibodies and immune checkpoint inhibitors, to redirect and/or unleash the NK cells against the leukemic cells.