Background Children with high body mass index (BMI) at preschool age are at risk of developing obesity. Early identification of factors that increase the risk of excessive weight gain could help direct preventive actions. The intestinal microbiota and antibiotic use have been identified as potential modulators of early metabolic programming and weight development. To test if the early microbiota composition is associated with later BMI, and if antibiotic use modifies this association, we analysed the faecal microbiota composition at 3 months and the BMI at 5–6 years in two cohorts of healthy children born vaginally at term in the Netherlands (N = 87) and Finland (N = 75). We obtained lifetime antibiotic use records and measured weight and height of all children. Results The relative abundance of streptococci was positively and the relative abundance of bifidobacteria negatively associated with the BMI outcome. The association was especially strong among children with a history of antibiotic use. Bacteroides relative abundance was associated with BMI only in the children with minimal lifetime antibiotic exposure. Conclusions The intestinal microbiota of infants are predictive of later BMI and may serve as an early indicator of obesity risk. Bifidobacteria and streptococci, which are indicators of microbiota maturation in infants, are likely candidates for metabolic programming of infants, and their influence on BMI appears to depend on later antibiotic use.