In major depressive disorder (MDD), cognitive dysfunctions strongly contribute to functional impairments but are barely addressed in current therapies. Novel treatment strategies addressing cognitive symptoms in depression are needed. As the gut microbiota-brain axis is linked to depression and cognition, we investigated the effect of a 4-week high-dose probiotic supplementation on cognitive symptoms in depression. This randomized controlled trial included 60 patients with MDD, of whom 43 entered modified intention-to-treat analysis. A probiotic supplement or indistinguishable placebo containing maltose was administered over 31 days in addition to treatment as usual for depression. Participant scores on the Verbal Learning Memory Test (VLMT), Corsi Block Tapping Test, and both Trail Making Test versions as well as brain-derived neurotrophic factor levels were assessed at 3 different time points: before, immediately after and 4 weeks after intervention. Additionally, brain activation changes during working memory processing were investigated before and immediately after intervention. We found a significantly improved immediate recall in the VLMT in the probiotic group immediately after intervention, and a trend for a time × group interaction considering all time points. Furthermore, we found a time × group interaction in hippocampus activation during working memory processing, revealing a remediated hippocampus function in the probiotic group. Other measures did not reveal significant changes. The modest sample size resulting from our exclusion of low-compliant cases should be considered. Additional probiotic supplementation enhances verbal episodic memory and affects neural mechanisms underlying impaired cognition in MDD. The present findings support the importance of the gut microbiota-brain axis in MDD and emphasize the potential of microbiota-related regimens to treat cognitive symptoms in depression. clinicaltrials.gov identifier NCT02957591.