BACKGROUND About one-third of people older than 65 years fall at least once a year. Physical exercise has been previously demonstrated to improve gait, enhance physical fitness, and prevent falls. Nonetheless, the addition of cognitive training components may potentially increase these effects, since cognitive impairment is related to gait irregularities and fall risk. We hypothesized that simultaneous cognitive-physical training would lead to greater improvements in dual-task (DT) gait compared to exclusive physical training. METHODS Elderly persons older than 70 years and without cognitive impairment were randomly assigned to the following groups: 1) virtual reality video game dancing (DANCE), 2) treadmill walking with simultaneous verbal memory training (MEMORY), or 3) treadmill walking (PHYS). Each program was complemented with strength and balance exercises. Two 1-hour training sessions per week over 6 months were applied. Gait variables, functional fitness (Short Physical Performance Battery, 6-minute walk), and fall frequencies were assessed at baseline, after 3 months and 6 months, and at 1-year follow-up. Multiple regression analyses with planned comparisons were carried out. RESULTS Eighty-nine participants were randomized to three groups initially; 71 completed the training and 47 were available at 1-year follow-up. DANCE/MEMORY showed a significant advantage compared to PHYS in DT costs of step time variability at fast walking (P=0.044). Training-specific gait adaptations were found on comparing DANCE and MEMORY: DANCE reduced step time at fast walking (P=0.007) and MEMORY reduced gait variability in DT and DT costs at preferred walking speed (both trend P=0.062). Global linear time effects showed improved gait (P<0.05), functional fitness (P<0.05), and reduced fall frequency (-77%, P<0.001). Only single-task fast walking, gait variability at preferred walking speed, and Short Physical Performance Battery were reduced at follow-up (all P<0.05 or trend). CONCLUSION Long-term multicomponent cognitive-physical and exclusive physical training programs demonstrated similar potential to counteract age-related decline in physical functioning.