Bacillus coagulans can help ameliorate or prevent gastrointestinal diseases, but the genetic relationships among B. coagulans isolates are not well studied. Multilocus sequence typing analysis was conducted on 57 isolates of B. coagulans from 22 provinces or autonomous regions in China. B. coagulans isolates were highly diverse and a total of 33 (sequence typings) STs were found. These isolates had a weak clonal population structure and strong indications of intraspecies recombination. The evolution direction of B. coagulans was not correlated with geography or isolation source. Fifteen strains were selected for further analysis based on proximity relationships from the phylogenetic tree. Five isolates (B. coagulans-1, B. coagulans-10, B. coagulans-39, B. coagulans-70 and B. coagulans-71) with good spore-forming ability relative to the rest of the isolates were evaluated for constipation relief. B. coagulans-39 significantly relieved constipation symptoms in mice by regulating intestinal flora, increasing the production of short-chain fatty acids and restoring the level of gastrointestinal regulatory peptides. Comparative genomic analysis showed the beneficial effects of B. coagulans-39 might be associated with specific functional genes that are involved in the utilization of various carbohydrates as primary substrates and short-chain fatty acid production.