Cognitive-motor dual-tasking is a complex activity that predicts falls risk and cognitive impairment in older adults. Cognitive and physical training can both lead to improvements in dual-tasking; however, less is known about what mechanisms underlie these changes. To investigate this, 33 healthy older adults were randomized to one of three training arms: Executive function (EF; n = 10), Aerobic Exercise (AE; n = 10), Gross Motor Abilities (GMA; n = 13) over 12 weeks (1 h, 3×/week). Single and dual-task performance (gait speed, m/s; cognitive accuracy, %) was evaluated before and after training, using the 2-back as concurrent cognitive load. Training arms were designed to improve cognitive and motor functioning, through different mechanisms (i.e., executive functioning – EF, cardiorespiratory fitness – CRF, and energy cost of walking – ECW). Compared to baseline, we observed few changes in dual-task gait speed following training (small effect). However, dual-task cognitive accuracy improved significantly, becoming facilitated by walking (large effect). There were no differences in the magnitude of improvements across training arms. We also found that older adults with lower cognitive ability (i.e., MoCA score