Consumers require fermented milk that possesses constipation-relieving functions. To cater to the 'natural and additive-free' consumption habit, this study is dedicated to developing probiotic fermented milk with constipation-relief effects. Previously, we isolated two Lactobacillus strains, Lactobacillus MWLp-12 and Lactobacillus MWLf-4, from breast milk. This study evaluated the efficacy of these strains and their fermented milk in alleviating constipation in a Balb/c mouse model of constipation. The evaluation criteria included fecal water content, time for first black feces expulsion and propulsion rate of the small intestine. The mechanisms of constipation relief were investigated using gastrointestinal regulatory peptides, colonic tissue pathology, short-chain fatty acid levels and gut microbiota analyses.