Studies report benefits of physical exercise and cognitive training to enhance cognition in older adults. However, most studies did not compare these interventions to appropriate active controls. Moreover, physical exercise and cognitive training seem to involve different mechanisms of brain plasticity, suggesting a potential synergistic effect on cognition. This study investigated the synergistic effect of cognitive training and aerobic/resistance physical exercise on dual-task performance in older adults. Intervention effects were compared to active controls for both the cognitive and the exercise domain. Eighty-seven older adults completed one of 4 different combinations of interventions, in which computer lessons was active control for cognitive training and stretching/toning exercise control for aerobic/resistance training: (a) cognitive dual-task training and aerobic/resistance training (COG+/AER+), (b) computer lessons and aerobic/resistance training (COG-/AER+), (c) cognitive dual-task training and stretching/toning exercises (COG+/AER-), and (d) computer lessons and stretching/toning exercises (COG-/AER-). The primary outcome was performance in an untrained transfer dual task. Stepwise backward removal regression analyses were used to predict pre- versus post-test changes in groups that have completed the dual-task training, aerobic/resistance or both interventions. Participation in AER+ did not predict improvement in any dual-task outcomes. Participation in COG+ predicted reduction in dual-task cost and participation in COG+/AER+ predicted reduction in task-set cost. Results suggest that the combination of cognitive and physical training protocols exerted a synergistic effect on task-set cost which reflects the cost of maintaining multiple response alternatives, whereas cognitive training specifically improved dual-task cost, which reflects the ability of synchronizing concurrent tasks.