Background/Objectives: Multi-strain Limosilactobacillus fermentum supplementation has been reported to promote weight loss outcomes in free-living conditions, but limited evidence exists on these probiotic strains added to an energy-restricted diet and walking program in overweight adults. Methods: In a double-blind, placebo-controlled, parallel-arm randomized trial, overweight adults (35.2 ± 13.2 years old, 167.6 ± 8.6 cm, 79.9 ± 11.8 kg, 28.4 ± 2.7 kg/m² body mass index, 36.1 ± 6.6% body fat) completed a 12-week weight loss program that included a 500 kcal/day energy deficit and walking 10 k steps/d. Participants ingested one daily capsule containing a three-strain probiotic blend (L. fermentum K7-Lb1, L. fermentum K8-Lb1, L. fermentum K11-Lb3; 6 billion CFU/day) (PRO) or maltodextrin placebo (PLA). Assessments were performed at baseline, week 6, and week 12 and included body composition, resting energy expenditure, substrate utilization, peak oxygen uptake, dietary intake, step counts, blood biomarkers, quality of life, and side effects. Data were analyzed using multivariate and univariate repeated-measures general linear models (GLM), with mean changes from baseline presented alongside 95% confidence intervals. Results: All participants significantly reduced body weight, fat mass, body fat percentage, and waist circumference. At 12 weeks, PRO reduced fat mass more than PL (−2680.7 ± 1276.7 g; p = 0.039). In PRO, android and gynoid fat percentage decreased at 6 weeks (p < 0.001; p = 0.008) and 12 weeks (p = 0.004; p < 0.001), respectively. Visceral adipose tissue mass, volume, and area were lower at 6 weeks and trended lower at 12 weeks. In PRO, bone mineral content and bone mineral area decreased at 12 weeks, while bone mineral density paradoxically increased (0.007 ± 0.003 g/cm²; p = 0.024). Conclusions: During a 12-week weight loss program, supplementation of a multi-strain L. fermentum probiotic significantly reduced body fat and central adiposity.