We conducted a phase 2 study to determine the efficacy of HLA-haploidentical related donor natural killer (NK) cells after cyclophosphamide-based lymphodepletion in patients with relapsed or progressive acute myelogenous leukemia (AML) or myelodysplastic syndrome (MDS) following allogeneic hematopoietic cell transplantation (HCT). Eight patients (2 with MDS and 6 with AML) were treated with cyclophosphamide 50 mg/kg on day −3 and day −2 before infusion of NK cells isolated from a haploidentical related donor. One patient also received fludarabine 25 mg/m²/day for 4 days. Six doses of 1 million units of interleukin-2 (IL-2) were administered on alternating days beginning on day −1. The median number of NK cells infused was 10.6 × 10⁶/kg (range, 4.3 to 22.4 × 10⁶/kg), and the median number of CD3 cells infused was 2.1 × 10³/kg (range, 1.9 to 40 × 10³/kg). NK infusions were well tolerated, with a median time to neutrophil recovery of 19 days (range, 7 days to not achieved) and no incidence of graft-versus-host disease after NK infusion. One patient with AML and 1 patient with MDS achieved a complete response, but relapsed at 1.7 and 1.8 months, respectively. One patient with MDS experienced resolution of dysplastic features but persistence of clonal karyotype abnormalities; this patient was stable at 65 months after NK cell therapy. The median duration of survival was 12.9 months (range, 0.8 to 65.3 months). Chimerism analysis of CD3⁻/CD56⁺ peripheral blood cells did not detect any circulating haploidentical NK cells after infusion. NK phenotyping was performed in 7 patients during and after IL-2 infusion. We found a slight trend toward greater expression of KIR2DL2/2DL3/2DS2 (5% versus 28%; P = .03) at 14 days in patients who survived longer than 6 months from NK cell infusion (n = 4) compared with those who died within 6 months of NK cell therapy (n = 3). In summary, our data support the safety of haploidentical NK cell infusion after allogeneic HCT.