The gut–brain axis plays a role in major depressive disorder (MDD). Gut-bacterial metabolites are suspected to reduce low-grade inflammation and influence brain function. Nevertheless, randomized, placebo-controlled probiotic intervention studies investigating metabolomic changes in patients with MDD are scarce. The PROVIT study (registered at clinicaltrials.com NCT03300440) aims to close this scientific gap. PROVIT was conducted as a randomized, single-center, double-blind, placebo-controlled multispecies probiotic intervention study in individuals with MDD (n = 57). In addition to clinical assessments, metabolomics analyses (1H Nuclear Magnetic Resonance Spectroscopy) of stool and serum, and microbiome analyses (16S rRNA sequencing) were performed. After 4 weeks of probiotic add-on therapy, no significant changes in serum samples were observed, whereas the probiotic groups’ (n = 28) stool metabolome shifted towards significantly higher concentrations of butyrate, alanine, valine, isoleucine, sarcosine, methylamine, and lysine. Gallic acid was significantly decreased in the probiotic group. In contrast, and as expected, no significant changes resulted in the stool metabolome of the placebo group. Strong correlations between bacterial species and significantly altered stool metabolites were obtained. In summary, the treatment with multispecies probiotics affects the stool metabolomic profile in patients with MDD, which sets the foundation for further elucidation of the mechanistic impact of probiotics on depression.