Different types of exercise training have the potential to induce structural and functional brain plasticity in the elderly. Thereby, functional brain adaptations were observed during cognitive tasks in functional magnetic resonance imaging studies that correlated with improved cognitive performance. This study aimed to investigate if exercise training induces functional brain plasticity during challenging treadmill walking and elicits associated changes in cognitive executive functions. Forty-two elderly participants were recruited and randomly assigned to either interactive cognitive-motor video game dancing (DANCE) or balance and stretching training (BALANCE). The 8-week intervention included three sessions of 30 min per week and was completed by 33 participants (mean age 74.9 ± 6.9 years). Prefrontal cortex (PFC) activity during preferred and fast walking speed on a treadmill was assessed applying functional near infrared spectroscopy pre- and post-intervention. Additionally, executive functions comprising shifting, inhibition, and working memory were assessed. The results showed that both interventions significantly reduced left and right hemispheric PFC oxygenation during the acceleration of walking (p < 0.05 or trend, r = 0.25-0.36), while DANCE showed a larger reduction at the end of the 30-s walking task compared to BALANCE in the left PFC [F (1, 31) = 3.54, p = 0.035, r = 0.32]. These exercise training induced modulations in PFC oxygenation correlated with improved executive functions (p < 0.05 or trend, r = 0.31-0.50). The observed reductions in PFC activity may release cognitive resources to focus attention on other processes while walking, which could be relevant to improve mobility and falls prevention in the elderly. This study provides a deeper understanding of the associations between exercise training, brain function during walking, and cognition in older adults.