Aims: The gut microbiota exerts a critical influence in the immune system. The gut microbiota of human virus immunodeficiency (HIV)-infected children remains barely explored. We aimed to characterize the fecal microbiota in vertically HIV-infected children and to explore the effects of its modulation with a symbiotic nutritional intervention. Methods: a pilot, double blind, randomized placebo-controlled study including HIV-infected children who were randomized to receive a nutritional supplementation including prebiotics and probiotics or placebo for four weeks. HIV-uninfected siblings were recruited as controls. The V3–V4 region of the 16S rRNA gene was sequenced in fecal samples. Results: 22 HIV-infected children on antiretroviral therapy (ART) and with viral load (VL) <50/mL completed the follow-up period. Mean age was 11.4 ± 3.4 years, eight (32%) were male. Their microbiota showed reduced alpha diversity compared to controls and distinct beta diversity at the genus level (Adonis p = 0.042). Patients showed decreased abundance of commensals Faecalibacterium and an increase in Prevotella, Akkermansia and Escherichia. The nutritional intervention shaped the microbiota towards the control group, without a clear directionality. Conclusions: Vertical HIV infection is characterized by changes in gut microbiota structure, distinct at the compositional level from the findings reported in adults. A short nutritional intervention attenuated bacterial dysbiosis, without clear changes at the community level. Summary: In a group of 24 vertically HIV-infected children, in comparison to 11 uninfected controls, intestinal dysbiosis was observed despite effective ART. Although not fully effective to restore the microbiota, a short intervention with pre/probiotics attenuated bacterial dysbiosis.