Background/Objectives: The relations between the gut microbiota and change in body mass index (BMI) or pediatric overweight in early life remain unclear and there is a scarcity of information regarding the preterm population. This study aimed to investigate how the gut microbiota at 3.5 years of age is associated with (1) the later BMI at 5 years, and (2) BMI z-score variations between 2 and 5 years in children from two French nationwide birth cohorts. Subjects/Methods: Bacterial 16S rRNA gene sequencing was performed to profile the gut microbiota at 3.5 years of very preterm children (n = 143, EPIPAGE 2 cohort) and late preterm/full-term children (n = 369, ELFE cohort). Predicted metabolic function abundances was computed using PICRUSt2 tool. Children anthropometric measurements were collected at 2 and 5 years through medical exams or retrieved from the child health booklets. Statistical analyses included multivariable linear and logistic regressions, variable selection using random forest, and microbiome regression-based kernel association tests. Results The Firmicutes to Bacteroidetes (F/B) ratio at 3.5 years was positively associated with BMI z-score at 5 years. Several genera were positively associated ( [Eubacterium] hallii group, Fusicatenibacter , and [Eubacterium] ventriosum group ) or negatively associated ( Eggerthella, Colidextribacter , and Ruminococcaceae CAG-352 ) with BMI z-score at 5 years. Some genera were also associated with BMI z-score variations between 2 and 5 years. Predicted metabolic functions including steroid hormone biosynthesis, biotin metabolism, glycosaminoglycan degradation, and amino sugar and nucleotide sugar metabolism were associated with a lower BMI z-score at 5 years. Biosynthesis of unsaturated fatty acids pathway was associated with a higher BMI z-score. Conclusions These findings indicate that the gut microbiota at 3.5 years is associated with later BMI during childhood independently of preterm or term birth suggesting that changes in the gut microbiota that may predispose to adult obesity begin in early childhood.