Extremely low birth weight (ELBW) infants often develop an altered gut microbiota composition, which is related to clinical complications, such as necrotizing enterocolitis and sepsis. Probiotic supplementation may reduce these complications, and modulation of the gut microbiome is a potential mechanism underlying the probiotic effectiveness. In a randomized, double-blind, placebo-controlled trial, we assessed the effect of Lactobacillus reuteri supplementation, from birth to post-menstrual week (PMW)36, on infant gut microbiota. We performed 16S amplicon sequencing in 558 stool samples from 132 ELBW preterm infants at 1 week, 2 weeks, 3 weeks, 4 weeks, PMW36, and 2 years. Probiotic supplementation results in increased bacterial diversity and increased L. reuteri abundance during the 1st month. At 1 week, probiotic supplementation also results in a lower abundance of Enterobacteriaceae and Staphylococcaceae. No effects were found at 2 years. In conclusion, probiotics may exert benefits by modulating the gut microbiota composition during the 1st month in ELBW infants.