Background/Objectives: Gastrointestinal dysmotility, abdominal discomfort, and feeding-related respiratory instability are common in preterm infants. Although locust bean gum (LBG)-containing formulas are used for regurgitation, their short-term effects on gastrointestinal tolerance in neonatal intensive care settings are not well defined. We evaluated short-term changes in gastrointestinal tolerance and oxygenation after initiation of an LBG-containing formula and explored whether postmenstrual age (PMA) modified the response. Methods: This retrospective paired cohort study included 26 infants who received an LBG-containing anti-regurgitation formula, either alone or combined with human milk. Standardized ordinal scores (0–2) for stool consistency, straining, abdominal distension, gas passage, abdominal tenderness, mean oxygen saturation (SpO2) category, and desaturation frequency were recorded at baseline (Day 0), Day 3, and Day 7. Paired comparisons were performed using the Wilcoxon signed-rank test, and PMA-stratified differences were explored using Kruskal–Wallis analysis. Results: By Day 7, soft/normal stools were observed in 96.2% of infants (p = 0.00017), severe straining resolved in 87.5% (p = 1.6 × 10−5), abdominal distension improved in 96.2% (p = 2.4 × 10−6), and gas passage normalized in all infants (p = 0.00025). Mean SpO2 category improved significantly (p = 0.0023), and the proportion of infants with rare or no desaturation increased from 61.5% to 96.2%. Growth velocity remained clinically acceptable. Infants with PMA < 34 weeks showed the largest improvements across outcomes. Conclusions: In this retrospective paired cohort, initiation of an LBG-containing formula was associated with short-term improvement in gastrointestinal tolerance and oxygenation indices in preterm infants. Exploratory subgroup analyses suggested possible heterogeneity of response across postmenstrual age strata; these observations require confirmation in adequately powered prospective studies.