NK cells recognize self-HLA via killer Ig-like receptors (KIR). Homeostatic HLA expression signals for inhibition via KIR, and downregulation of HLA, a common consequence of viral infection, allows NK activation. Like HLA, KIR are highly polymorphic, and allele combinations of the most diverse receptor–ligand pair, KIR3DL1 and HLA-B, correspond to hierarchical HIV control. We used primary cells from healthy human donors to demonstrate how subtype combinations of KIR3DL1 and HLA-B calibrate NK education and their consequent capacity to eliminate HIV-infected cells. High-density KIR3DL1 and Bw4-80I partnerships endow NK cells with the greatest reactivity against HLA-negative targets; NK cells exhibiting the remaining KIR3DL1/HLA-Bw4 combinations demonstrate intermediate responsiveness; and Bw4-negative KIR3DL1+ NK cells are poorly responsive. Cytotoxicity against HIV-infected autologous CD4+ T cells strikingly correlated with reactivity to HLA-negative targets. These findings suggest that the programming of NK effector function results from defined features of receptor and ligand subtypes. KIR3DL1 and HLA-B subtypes exhibit an array of binding strengths. Like KIR3DL1, subtypes of HLA-Bw4 are expressed at distinct, predictable membrane densities. Combinatorial permutations of common receptor and ligand subtypes reveal binding strength, receptor density, and ligand density to be functionally important. These findings have immediate implications for prognosis in patients with HIV infection. Furthermore, they demonstrate how features of KIR and HLA modified by allelic variation calibrate NK cell reactive potential.