Aging is accompanied by an alteration in the capacity to ambulate, react to external balance perturbations, and resolve cognitive tasks. Perturbation-based balance training has been used to induce adaptations of gait stability and reduce fall risk. The compensatory reactions generated in response to external perturbations depend on the activation of specific neural structures. This suggests that training balance recovery reactions should show acute cognitive training effects. This study aims to investigate whether exposure to repeated balance perturbations while walking can produce acute aftereffects that improve proactive and reactive strategies to control gait stability and cognitive performance in healthy older adults. It is expected that an adaptation of the recovery reactions would be associated with increased selective attention and information processing speed. Twenty-eight healthy older adults were assigned to either an Experimental (EG) or a Control Group (CG). The protocol was divided in 2 days. During the first visit, all participants completed the Symbol Digit Modalities Test (SDMT) and the Trail Making Test (TMT). During the second visit, a cable-driven robot was used to apply waist-pull perturbations while walking on a treadmill. The EG was trained with multidirectional perturbations of increasing intensity. The CG walked for a comparable amount of time with cables on, but without experiencing perturbations. Before and after the training, all participants were exposed to diagonal waist-pull perturbations. Changes in gait stability were evaluated by comparing the distance between the heel of the leading leg and the extrapolated Center of Mass (Heel-XCoM Distance—HXD) at perturbation onset (PON) and first compensatory heel strike (CHS). Finally, the cables were removed, and participants completed the SDMT and the TMT again. Results showed that only the EG adapted the gait stability (p < 0.001) in reaction to diagonal perturbations and showed improved performance in the SDMT (p < 0.001). This study provides the first evidence that a single session of perturbation-based balance training produce acute aftereffects in terms of increased cognitive performance and gait stability in healthy older adults. Future studies will include measures of functional activation of the cerebral cortex and examine whether a multi-session training will demonstrate chronic effects.