Abstract Background Up to 40% of HIV-infected individuals receiving Highly Active Antiretroviral Therapy (HAART) have poor CD4+ T-cell recovery. The role of natural killer (NK) cells in immune recovery during HAART is not well understood. We described the profiles of NK cell subsets and their expression of activating receptor, NKG2D and cytotoxicity receptor NKp46 among suboptimal immune responders to despite four years of suppressive HAART. Methods A case control study utilized frozen peripheral blood mononuclear cells (PBMC) from a cohort of HIV-infected adults that initiated HAART in 2004/5, at CD4 < 200 cells/μl. Cases were ‘suboptimal’ responders; patients within the lowest quartile of CD4+ T-cell reconstitution, with a median CD4 count increase of 129 (-43-199) cells/μl (difference between CD4 count at baseline and after 4 years of HAART) and controls were ‘super-optimal’ responders; patients within the highest quartile of CD4 T-cell reconstitution with a median CD4 count increase of 528 (416-878) cells/μl). Expression of NK cell lineage markers (CD56+/-CD16+/-) and receptors NKG2D and NKp46, was measured among PBMC from 29 cases of ‘suboptimal’ responders’ and 23 controls of ‘super-optimal responders’, and compared among ‘suboptimal’ and ‘super-optimal’ responders. NK cell populations were compared using the Holm Sidak multiple comparison test and p values < 0.05 were considered statistically significant. Data was analyzed using FLOWJO and GraphPad Prism 6. Results ‘Suboptimal responders’ had a higher proportion of cytokine producing CD56++CD16+/- (CD56bri) NK cells than the ‘super-optimal responders’ p = 0.017, and CD56neg NK cells were lower among suboptimal than super-optimal responders (p = 0.007). The largest NK cell subset, CD56dim, was comparable among suboptimal responders and ‘super-optimal immune responders’. Expression of NKG2D and NKp46 receptors on NK cell subsets (CD56bri, CD56neg and CD56dim), was comparable among ‘suboptimal’ and ‘super-optimal’ immune responders. Conclusions The pro-inflammatory CD56++CD16-- NK cells were higher among ‘suboptimal’ responders relative to ‘super-optimal’ responders, despite four years of suppressive HAART. Alteration of NK cell populations could inhibit host immune responses to infections among suboptimal responders. We recommend further analysis of NK cell function among suboptimal immune responders in order to inform targeted interventions to optimize immune recovery among HAART-treated adults.