Although gait-related dual-task interference in aging is well established, the effect of gait and cognitive task difficulty on dual-task interference is poorly understood. The purpose of this study was to examine the effect of gait and cognitive task difficulty on cognitive-motor interference in aging. Fifteen older adults (72.1 years, SD 5.2) and 20 young adults (21.7 years, SD 1.6) performed three walking tasks of varying difficulty (self-selected speed, fast speed, and fast speed with obstacle crossing) under single- and dual-task conditions. The cognitive tasks were the auditory Stroop task and the clock task. There was a significant Group×Gait Task×Cognitive Task interaction for the dual-task effect on gait speed. After adjusting for education, there were no significant effects of gait or cognitive task difficulty on the dual-task effects on cognitive task performance. The results of this study provide evidence that gait task difficulty influences dual-task effects on gait speed, especially in older adults. Moreover, the effects of gait task difficulty on dual-task interference appear to be influenced by the difficulty of the cognitive task. Education is an important factor influencing cognitive-motor interference effects on cognition, but not gait.