Recent studies suggest that innate immune responses by natural killer (NK) cells play a significant role in restricting human immunodeficiency virus type-1 (HIV-1) pathogenesis. Our aim was to characterize changes in NK cells associated with HIV-1 clade C disease progression. Here we used multiparametric flow cytometry (LSRII) to quantify phenotype and function of NK cells in a cross-sectional analysis of cryopreserved blood samples from a cohort of 41 chronically HIV-1-infected, treatment-naive adult South Africans. These individuals ranged in disease severity from early (CD4 count >500) to advanced HIV-1 disease (CD4 count <50). We found that the frequency of NK cells expressing KIR2DL1, an inhibitory receptor, and/or KIR2DS1, an activating receptor, tended to decrease with increasing HIV-1 viral load. We also discovered a significant increase (p < 0.05) in overall NK cell degranulation with disease progression. We found that acutely activated NK cells (CD69(pos)) were deficient in NKp46 expression ex vivo. In conclusion, we observed that with viremia and advanced HIV-1 disease, activated NK cells lack NKp46 expression, and KIR2DS1(pos) and/ or KIR2DL1(pos) NK cells are reduced in frequency. These findings suggest that modulation of receptor expression on NK cells may play a role in HIV-1 pathogenesis, and provide new insights on immunological changes in advanced HIV-1 disease.