This study aimed to investigate the effects of supervised exercise training (SET) on walking performance and spatiotemporal gait changes in patients with symptomatic lower extremity peripheral artery disease (PAD). In this single-arm prospective nonrandomized cohort study, patients with Fontaine stage II PAD following a 3-month SET program were included. Before and after SET, a constant-load treadmill test was performed to determine the pain-free and maximal walking distances (PFWD and MWD, respectively). During this test, spatiotemporal gait parameters were assessed. The ankle-brachial index (ABI) and toe-brachial index (TBI) were also measured. Twenty-seven patients with PAD (64.0 ± 1.9 y, 74% men) were included. Following SET, the PFWD (+68%; p = 0.001) and MWD (+79%; p ⩽ 0.001) significantly increased. The ABI and TBI did not change significantly. Following SET, the stride duration, stride frequency, stride length, and double support phase duration did not change significantly. In contrast, subphases of stance showed significant changes: the loading response (+8%; p = 0.03) and foot-flat (+2%; p = 0.01) phases were significantly longer, whereas the push-off phase (-7%; p = 0.002) was significantly shorter. A significant positive correlation was found between changes in the foot-flat phase and changes in PFWD (r = 0.43, p = 0.03). A significant negative correlation was found between changes in the push-off phase and changes in PFWD (r = -0.39, p = 0.05). No significant correlations were found between changes in relative durations of the subphases of stance and MWD. These results indicate that changes in temporal gait parameters during the foot contact phase potentially constitute an underlying mechanism of delayed claudication distance in patients with symptomatic PAD.