Objective: Attention and executive function are associated with dual task-related gait changes in older adults, which increases risk of falls. We investigate the impact of structured interventions on gait speed and stride, and an attentional task in cognitively healthy older adults. Method: Community-dwelling adults (65 years and older) were randomly assigned to one of four intervention programs: cognitive, physical exercise, mindfulness, or control. Each intervention was 35 min/day, 5 days/week, over 5 weeks. Before and after each intervention, subjects completed two single tasks walking 8 meters or serial subtractions, and a dual task requiring that both be done simultaneously. Time, number of steps, and number of correct and incorrect serial 3 responses were recorded to compare performance between groups pre- and post-intervention. Results: Participants (n = 40, mean age 76.4) walked slower in the dual task than single task condition F(1,36) = 45.18, p < .001, 95% CI [3.88, 7.22]. Participants in the exercise condition took fewer steps during the post-intervention dual-task compared to pre, p = .03, 95% CI [−1.71, −0.09]. Participants in the cognitive and control groups generated more correct responses during the single task post-intervention, p = .04, 95% CI [0.14, 3.3]; p = .04, 95% CI [0.04, 1.60], respectively. Conclusion: Exercise training increased length of step in a dual walking-serial 3 task. Both adaptive and non-adaptive cognitive training was associated with increased performance of serial 3 responses under the single task condition. Improvements in cognition and mobility, which decline with aging, are valued outcomes of the tested interventions in an elderly population.