The ability of cord blood transplantation (CBT) to prevent relapse depends partly on donor natural killer (NK) cell alloreactivity. NK effector function depends on specific killer-cell immunoglobulin-like receptors (KIR) and HLA interactions. Thus, it is important to identify optimal combinations of KIR-HLA genotypes in donors and recipients that could improve CBT outcome. We studied clinical data, KIR and HLA genotypes, and NK-cell reconstitution in CBT patients (n = 110). Results were validated in an independent cohort (n = 94). HLA-KIR genotyping of recipient germline and transplanted cord blood (CB) grafts predicted for large differences in outcome. Patients homozygous for HLA-C2 group alleles had higher 1-year relapse rate and worse survival after CBT than did HLA-C1/C1 or HLA-C1/C2 (HLA-C1/x) patients: 67.8% vs 26.0% and 15.0% vs 52.9%, respectively. This inferior outcome was associated with delayed posttransplant recovery of NK cells expressing the HLA-C2-specific KIR2DL1/S1 receptors. HLA-C1/x patients receiving a CB graft with the combined HLA-C1-KIR2DL2/L3/S2 genotype had lower 1-year relapse rate (6.7% vs 40.1%) and superior survival (74.2% vs 41.3%) compared with recipients of grafts lacking KIR2DS2 or HLA-C1. HLA-C2/C2 patients had lower relapse rate (44.7% vs 93.4%) and better survival (30.1% vs 0%) if they received a graft with the combined HLA-C2-KIR2DL1/S1 genotype. Relapsed/refractory disease at CBT, recipient HLA-C2/C2 genotype, and donor HLA-KIR genotype were independent predictors of outcome. Thus, we propose the inclusion of KIR genotyping in graft selection criteria for CBT. HLA-C1/x patients should receive an HLA-C1-KIR2DL2/L3/S2 CB graft, while HLA-C2/C2 patients may benefit from an HLA-C2-KIR2DL1/S1 graft.