Natural killer (NK) cells are important innate effector cells controlled by an array of activating and inhibitory receptors. Some alleles of the inhibitory killer-cell immunoglobulin-like receptor KIR3DL1 in combination with its HLA class I ligand Bw4 have been genetically associated with slower HIV-1 disease progression. Here, we observed that the presence of HLA-B Bw4 was associated with elevated frequencies of KIR3DL1(+) CD56(dim) NK cells in chronically HIV-1-infected individuals from the rural district of Kayunga, Uganda. In contrast, levels of KIR2DL1(+) CD56(dim) NK cells were decreased, and levels of KIR2DL3(+) CD56(dim) NK cells were unchanged in infected subjects carrying their respective HLA-C ligands. Furthermore, the size of the KIR3DL1(+) NK cell subset correlated directly with viral load, and this effect occurred only in HLA-B Bw4(+) patients, suggesting that these cells expand in response to viral replication but may have relatively poor antiviral capacity. In contrast, no association with viral load was present for KIR2DL1(+) and KIR2DL3(+) NK cells. Interestingly, chronic HIV-1 infection was associated with an increased polyfunctional response in the NK cell compartment, and, upon further investigation, KIR3DL1(+) CD56(dim) NK cells exhibited a significantly increased functional response in the patients carrying HLA-B Bw4. These results indicate that chronic HIV-1 infection is associated with increased NK cell polyfunctionality and elevated levels of KIR3DL1(+) NK cells in Ugandans carrying the HLA-B Bw4 motif.