Constipation is a common and burdensome gastrointestinal disorder that may result from altered gastrointestinal motility. The effect of probiotics on constipation has been increasingly investigated in both animal and human studies, showing promising results. However, there is still uncertainty regarding the mechanisms of action of probiotics on gut motility and constipation. Several factors are vital to normal gut motility, including immune and nervous system function, bile acid metabolism and mucus secretion, and the gastrointestinal microbiota and fermentation; an imbalance or dysfunction in any of these components may contribute to aberrant gut motility and, consequently, symptoms of constipation. For example, adults with functional constipation have significantly decreased numbers of bifidobacteria (with one study showing a mean difference of 1 log/g) and lactobacilli (mean difference, 1.4 log/g) in stool samples, as well as higher breath methane, compared with control subjects. Modifying the gut luminal environment with certain probiotic strains may affect motility and secretion in the gut and, hence, provide a benefit for patients with constipation. Therefore, this review explores the mechanisms through which probiotics may exert an effect on gut motility and constipation. Nevertheless, the majority of current evidence is derived from animal studies, and therefore, further human studies are needed to determine the mechanisms through specific probiotic strains that might be effective in constipation.