Abstract Background While many studies confirm the positive effect of cognitive and physical training on cognitive performance of older adults, only little is known about the effects of simultaneously performed cognitive and physical training. In the current study, older adults simultaneously performed a verbal working memory and a cardiovascular training to improve cognitive and motor-cognitive dual task performance. Twenty training sessions of 30 minutes each were conducted over a period of ten weeks, with a test session before, in the middle, and after the training. Training gains were tested in measures of selective attention, paired-associates learning, executive control, reasoning, memory span, information processing speed, and motor-cognitive dual task performance in the form of walking and simultaneously performing a working memory task. Results Sixty-three participants with a mean age of 71.8 ± 4.9 years (range 65 to 84) either performed the simultaneous training ( N =  21), performed a single working memory training ( N  = 16), or attended no training at all ( N  = 26). The results indicate similar training progress and larger improvements in the executive control task for both training groups when compared to the passive control group. In addition, the simultaneous training resulted in larger improvements compared to the single cognitive training in the paired-associates task and was able to reduce the step-to-step variability during the motor-cognitive dual task when compared to the single cognitive training and the passive control group. Conclusions The simultaneous training of cognitive and physical abilities presents a promising training concept to improve cognitive and motor-cognitive dual task performance, offering greater potential on daily life functioning, which usually involves the recruitment of multiple abilities and resources rather than a single one.