Gait is an attention-demanding task even in healthy young adults. However, scant evidence exists about the attentional load required at various walking speeds. The aim of this study was to investigate motor-cognitive interference while walking at spontaneous, slow and very slow speed on a treadmill while carrying out a backward counting task, in a group (n = 22) of healthy young participants. Cognitive performance was also assessed while sitting. Higher DT cost on the cognitive task was found at spontaneous and very slow walking speed, while at slow walking speed the cognitive task was prioritized with higher DT cost on the motor task. The attentional allocation during DT depends on walking speed with gait prioritization at spontaneous and very slow speed that likely represent more challenging motor conditions.