Extracellular β-amyloid (Aβ) plaques and neurofibrillary tangles (NFTs) are the pathological hallmarks of Alzheimer’s disease (AD). Mesenchymal stem cells (MSCs) have shown therapeutic efficacy in many neurodegenerative diseases, including AD. Human menstrual blood-derived stem cells (MenSCs) are a novel source of MSCs advantageous for their higher proliferation rate and because they are easy to obtain without ethical concerns. Although MenSCs have exhibited therapeutic efficacy in some diseases, their effects on AD remain elusive. In the present study, we showed that intracerebral transplantation of MenSCs dramatically improved the spatial learning and memory of APP/PS1 mice. In addition, MenSCs significantly ameliorated amyloid plaques and reduced tau hyperphosphorylation in APP/PS1 mice. Remarkably, we also found that intracerebral transplantation of MenSCs markedly increased several Aβ degrading enzymes and modulated a panel of proinflammatory cytokines associated with an altered microglial phenotype, suggesting an Aβ degrading and anti-inflammatory impact of MenSCs in the brains of APP/PS1 mice. In conclusion, these findings suggest that MenSCs are a promising therapeutic candidate for AD.