In an exploratory, block-randomised, parallel, double-blind, single-centre, placebo-controlled superiority study (ISRCTN12562026, funded by Cultech Ltd), 220 Bulgarian participants (30 to 65 years old) with BMI 25–34.9 kg/m2 received Lab4P probiotic (50 billion/day) or a matched placebo for 6 months. Participants maintained their normal diet and lifestyle. Primary outcomes were changes in body weight, BMI, waist circumference (WC), waist-to-height ratio (WtHR), blood pressure and plasma lipids. Secondary outcomes were changes in plasma C-reactive protein (CRP), the diversity of the faecal microbiota, quality of life (QoL) assessments and the incidence of upper respiratory tract infection (URTI). Significant between group decreases in body weight (1.3 kg, p < 0.0001), BMI (0.045 kg/m2, p < 0.0001), WC (0.94 cm, p < 0.0001) and WtHR (0.006, p < 0.0001) were in favour of the probiotic. Stratification identified greater body weight reductions in overweight subjects (1.88%, p < 0.0001) and in females (1.62%, p = 0.0005). Greatest weight losses were among probiotic hypercholesterolaemic participants (−2.5%, p < 0.0001) alongside a significant between group reduction in small dense LDL-cholesterol (0.2 mmol/L, p = 0.0241). Improvements in QoL and the incidence rate ratio of URTI (0.60, p < 0.0001) were recorded for the probiotic group. No adverse events were recorded. Six months supplementation with Lab4P probiotic resulted in significant weight reduction and improved small dense low-density lipoprotein-cholesterol (sdLDL-C) profiles, QoL and URTI incidence outcomes in overweight/obese individuals.