Obesity is characterized by low-grade inflammation and increased gut permeability. Here, we aim to evaluate the effect of a nutritional supplement on these parameters in subjects with overweight and obesity. A double-blinded, randomized clinical trial was conducted in 76 adults with overweight or obesity (BMI 28 to 40) and low-grade inflammation (high-sensitivity C-reactive protein (hs-CRP) between 2 and 10 mg/L). The intervention consisted of a daily intake of a multi-strain probiotic of Lactobacillus and Bifidobacterium, 640 mg of omega-3 fatty acids (n-3 FAs), and 200 IU of vitamin D (n = 37) or placebo (n = 39), administered for 8 weeks. hs-CRP levels did not change post-intervention, other than an unexpected slight increase observed in the treatment group. Interleukin (IL)-6 levels decreased in the treatment group (p = 0.018). The plasma fatty acid (FA) levels of the arachidonic acid (AA)/eicosapentaenoic acid (EPA) ratio and n-6/n-3 ratio (p < 0.001) decreased, and physical function and mobility improved in the treatment group (p = 0.006). The results suggest that hs-CRP may not be the most useful inflammatory marker, but probiotics, n-3 FAs, and vitamin D, as non-pharmaceutical supplements, may exert modest effects on inflammation, plasma FA levels, and physical function in patients with overweight and obesity and associated low-grade inflammation.