Fatigue is a key factor that affects human motion and modulates physiology, biochemistry, and performance. Prolonged cyclic human movements (locomotion primarily) are characterized by a regular pattern, and this extended activity can induce fatigue. However, the relationship between fatigue and regularity has not yet been extensively studied. Wearable sensor methodologies can be used to monitor regularity during standardized treadmill tests (e.g., the widely used Bruce test) and to verify the effects of fatigue on locomotion regularity. Our study on 50 healthy adults [27 males and 23 females; <40 years; five dropouts; and 22 trained (T) and 23 untrained (U) subjects] showed how locomotion regularity follows a parabolic profile during the incremental test, without exception. At the beginning of the trial, increased walking speed in the absence of fatigue is associated with increased regularity (regularity index, RI, a. u., null/unity value for aperiodic/periodic patterns) up until a peak value (RI = 0.909 after 13.8 min for T and RI = 0.915 after 13.4 min for U subjects; median values, n. s.) and which is then generally followed (after 2.8 and 2.5 min, respectively, for T/U, n. s.) by the walk-to-run transition (at 12.1 min for both T and U, n. s.). Regularity then decreases with increased speed/slope/fatigue. The effect of being trained was associated with significantly higher initial regularity [0.845 (T) vs 0.810 (U), p < 0.05 corrected], longer test endurance [23.0 min (T) vs 18.6 min (U)], and prolonged decay of locomotor regularity [8.6 min (T) vs 6.5 min (U)]. In conclusion, the monitoring of locomotion regularity can be applied to the Bruce test, resulting in a consistent time profile. There is evidence of a progressive decrease in regularity following the walk-to-run transition, and these features unveil significant differences among healthy trained and untrained adult subjects.