Interactions between killer-immunoglobulin-like receptors (KIRs) and their HLA class I ligands are instrumental in natural killer (NK) cell regulation and protect normal tissue from NK cell attack. Human KIR haplotypes comprise genes encoding mainly inhibitory receptors (KIR A) or activating and inhibitory receptors (KIR B). A substantial fraction of humans lack ligands for inhibitory KIRs (iKIRs), that is, a ‘missing ligand' genotype. KIR B/x and missing ligand genotypes may thus give rise to potentially autoreactive, unlicensed NK cells. Little is known regarding the impact of such genotypes in untransplanted acute myeloid leukemia (AML). For this study, NK cell phenotypes and KIR/HLA genotypes were determined in 81 AML patients who received immunotherapy with histamine dihydrochloride and low-dose IL-2 for relapse prevention (NCT01347996). We observed that presence of unlicensed NK cells impacted favorably on clinical outcome, in particular among patients harboring functional NK cells reflected by high expression of the natural cytotoxicity receptor (NCR) NKp46. Genotype analyses suggested that the clinical benefit of high NCR expression was restricted to patients with a missing ligand genotype and/or a KIR B/x genotype. These data imply that functional NK cells are significant anti-leukemic effector cells in patients with KIR/HLA genotypes that favor NK cell autoreactivity.