Innate immune cells are important players during an infection. The frequency of monocytes, myeloid-derived suppressor cells (MDSCs), natural killer (NK), and NKT cells were assessed in blood samples of children and adolescents living with HIV (CALHIV) and HIV-uninfected (HU) children. Blood samples from 10 CALHIV (treated or not) and six HU individuals were collected for approximately one year. Flow cytometry was employed to phenotypically characterize cell populations. We found a lower frequency of classical monocytes in CALHIV patients compared to the HU group (35.75% vs. 62.60%, respectively) but a higher frequency of CD56-CD16+ NK cells in CALHIV patients compared to the HU group (1.45% vs. 0.44%, respectively). At baseline, the frequency of monocytic-MDSCs inversely correlated with CD56dimCD16+ NK cells (r= -0.73, p=0.020), CD56-CD16+ NK cells (r= -0.78, p=0.010), and with intermediate monocytes (r= -0.71, p=0.027) in the CALHIV group. We also found a negative correlation between CD56++CD16+- and CD56dimCD16+ NK cells with CD4 T cells frequency at baseline. The results suggest an alteration in the innate compartment of the CALHIV cohort, which may contribute to their susceptibility to infections.