Dual-task related gait changes have been previously reported for healthy older adults, suggesting that gait control requires attention. Compared to balance control, the involvement of attention in the control of the rhythmic stepping mechanism, as reflected by stride time variability, is not well known. In particular, under dual-task, the relative contributions of a second, attention-demanding task and changes in walking speed remain unclear. Thus, the aims of this study were (1) to assess whether walking with a slow-selected speed or walking while performing an attention-demanding task affected stride time variability in a sample of healthy older participants, and (2) to establish whether stride time variability under dual-task conditions is related either to the decrease of walking speed or the simultaneous attention-demanding task, or to both. Forty-five healthy older participants performed four experimental conditions: (1) walking at a normal self-selected speed, (2) walking at a slow self-selected speed, (3) performing a verbal fluency task when sitting on a chair, and (4) performing the verbal fluency task while walking at self-selected walking speed. Gait parameters were recorded across 15 meters, using Physilog. Results showed a significant dual-task related decrease in mean values of stride velocity, as well as a significant increase in mean values and coefficients of variation of stride time. These dual-task related changes in stride time were explained by the simultaneous performance of the verbal fluency task, the decrease of gait speed and the variability between participants. Although a relationship exists between decreased walking speed and increased stride time variability, the dual-task related increase of stride time variability was also significantly associated with the attention-demanding task, suggesting some attentional control for the rhythmic stepping mechanism of walking in healthy older adults.