The lack of affordable and effective therapeutics against cognitive impairment has promoted research toward alternative approaches to the treatment of neurodegeneration. In recent years, a bidirectional pathway that allows the gut to communicate with the central nervous system has been recognized as the gut-brain axis. Alterations in the gut microbiota, a dynamic population of trillions of microorganisms residing in the gastrointestinal tract, have been implicated in a variety of pathological states, including neurodegenerative disorders such as Alzheimer’s disease (AD). However, probiotic treatment as an affordable and accessible adjuvant therapy for the correction of dysbiosis in AD has not been thoroughly explored. Here, we sought to correct the dysbiosis in an AD mouse model with probiotic supplementation, with the intent of exploring its effects on disease progression. Transgenic 3xTg-AD mice were fed a control or a probiotic diet (Lactobacillus plantarum KY1032 and Lactobacillus curvatus HY7601) for 12 weeks, with the latter leading to a significant increase in the relative abundance of Bacteroidetes. Cognitive functions were evaluated via Barnes Maze trials and improvements in memory performance were detected in probiotic-fed AD mice. Neural tissue analysis of the entorhinal cortex and hippocampus of 10-month-old 3xTg-AD mice demonstrated that astrocytic and microglial densities were reduced in AD mice supplemented with a probiotic diet, with changes more pronounced in probiotic-fed female mice. In addition, elevated numbers of neurons in the hippocampus of probiotic-fed 3xTg-AD mice suggested neuroprotection induced by probiotic supplementation. Our results suggest that probiotic supplementation could be effective in delaying or mitigating early stages of neurodegeneration in the 3xTg-AD animal model. It is vital to explore new possibilities for palliative care for neurodegeneration, and probiotic supplementation could provide an inexpensive and easily implemented adjuvant clinical treatment for AD.