HIV infection is controlled immunologically in a small subset of infected individuals without antiretroviral therapy (ART), though the mechanism of control is unclear. CD8+ T cells are a critical component of HIV control in many immunologic controllers. NK cells are also believed to have a role in controlling HIV infection, though their role is less well-characterized. We used mass cytometry to simultaneously measure expression of 24 surface markers on peripheral NK cells from HIV-infected subjects with varying degrees of HIV natural control; we then used machine learning to identify NK cell subpopulations that differentiate HIV controllers from non-controllers. Using CITRUS (Cluster identification, characterization, and regression), we identified 3 NK cell subpopulations that differentiated subjects with chronic HIV viremia (Viremic Non-Controllers, VNC) from individuals with undetectable HIV viremia without ART (Elite Controllers, EC). In a parallel approach, we identified 11 NK cell subpopulations that differentiated HIV-infected subject groups using k-means clustering after dimensionality reduction by t-neighbor Stochastic Neighbor Embedding (tSNE) or Linear Discriminant Analysis (LDA). Of these additional 11 subpopulations, the frequencies of 5 correlated with HIV DNA levels; importantly, significance was retained in 2 subpopulations when only including cohorts without detectable viremia. By comparing the surface marker expression patterns of all identified subpopulations, we revealed that the CD11b+CD57-CD161+Siglec-7+ subpopulation of CD56dimCD16+ NK cells are more abundant in EC and HIV-negative controls compared to VNC, and the frequency of these cells correlated with HIV DNA levels. We hypothesize that this population may have a role in immunologic control of HIV infection. [ABSTRACT FROM AUTHOR]