Children born to pregnant women with HIV who are HIV-exposed but uninfected (HEU) are at an increased risk of growth stunting, morbidity, and mortality compared to HIV-unexposed children. Altered humoral and innate immune responses in HEU children may predispose them to recurrent infections and poor growth. However, the biological mechanisms driving immune abnormalities and growth deficits in HEU children remain poorly understood but may be linked to differences in the composition and function of the gut microbiome. We investigated links between the gut microbiome and early childhood growth in a prospective cohort of 168 HEU and HIV-unexposed children. We analyzed longitudinal quarterly growth measures from child age 3 months to 2 years, stool shotgun metagenomic data at 3 months’ age, and paired maternal rectal swab metagenomics for 75 participant pairs. As expected, infant stool microbiomes were characterized by four major clusters: Bifidobacterium longum, Escherichia coli, B. breve/bifidum, and Ruminococcus gnavus. While maternal HIV serostatus was not a major determinant of overall infant microbiome composition, it was associated with disturbances of potential opportunistic pathogens, including a higher presence of Corynebacterium xerosis, C. aurimucosum, and Enterococcus faecium, and a lower presence of Actinomyces urogenitalis and Veillonella seminalis. Slower length growth was linked to higher presence and abundance of Streptococcus pneumoniae, which causes pneumococcal pneumonia and other serious infections, and enriched abundance of Dolosigranulum pigrum, which can cause respiratory infections. A random forest model showed that the infant microbiome corresponded with 7.3% of the variation (95% CI: 7.0%-7.5%) in the individual length growth slopes. Finally, a greater abundance of B. breve was associated with greater length growth in children born to HIV-seronegative mothers, compared to those born to HIV-seropositive mothers, suggesting that maternal HIV serostatus may modulate the effects of microbiome on growth. Our findings expand the understanding of microbiome-related mechanisms underlying growth in HEU children and offer promising targets for interventions.