Carriage of the natural killer (NK) receptor genotype KIR3DL1*h/*y with its HLA-B*57 ligand (*h/*y+B*57) is associated with slow time to AIDS and low viral load (VL). To provide a functional basis for these epidemiological observations, we assessed whether HIV-1-infected slow progressors (SP) carrying the *h/*y+B*57 compound genotype would have increased NK cell polyfunctional potential in comparison to SP with other killer immunoglobulin-like receptor (KIR)/HLA compound genotypes and whether this enhanced polyfunctionality was dependent upon the coexpression of both KIR3DL1*h/*y and HLA-B*57. The functional potential of NK cells was investigated by stimulating peripheral blood mononuclear cells with HLA-devoid targets or single HLA transfectants. Multiparametric flow cytometry was used to detect NK cells with seven functional profiles representing all permutations of CD107a expression and gamma interferon (IFN-γ) and tumor necrosis factor alpha (TNF-α) secretion. NK cells from individuals carrying KIR3DL1 receptor-HLA-Bw4 ligand pairs had greater trifunctional responses than those from KIR3DL1 homozygotes (hmz), who were Bw6 homozygotes. NK cells from subjects carrying the *h/*y+B*57 genotypes exhibited the highest trifunctional potential, and this was dependent on cocarriage of the NK receptor and its ligand. Trifunctional cells secreted more of each function tested on a per-cell basis than each corresponding monofunctional NK subset. Although VL influenced NK functionality, individuals with defined KIR/HLA genotypes exhibited differences in NK cell polyfunctionality that could not be accounted for by VL alone. The protective effect of HLA-B*57 on slow progression to AIDS and low VL may be mediated through its interaction with KIR3DL1 alleles to educate NK cells for potent activity upon stimulation.