Objective To compare training and follow-up effects of combined aerobic and strength training versus aerobic-only training on cognitive and motor function in institutionalized patients with dementia and to explore whether improved motor function mediates improved cognitive function. Methods Using a 9-week, parallel, three-group, single-blind, randomized, controlled trial with a follow-up assessment at week 18, we assessed 109 patients with dementia (age 85.5 ± 5.1 years) in a psycho-geriatric nursing home. Each 9-week intervention consisted of 36, 30-minute sessions. A combined group (N = 37) received and completed two strength and two walking sessions per week, an aerobic group (N = 36) completed four walking sessions, and a social group (N = 36) completed four social visits per week. Cognitive and motor functions were assessed at baseline, after the 9-week intervention, and after a consecutive 9 weeks of usual care. Results Baseline corrected post-test scores in the combined versus the social group were higher for global cognition, visual memory, verbal memory, executive function, walking endurance, leg muscle strength, and balance. Aerobic versus social group scores were higher for executive function. Follow-up effects reversed toward baseline values. Motor improvement did not significantly mediate cognitive improvement. Conclusion Compared with a nonexercise control group, a combination of aerobic and strength training is more effective than aerobic-only training in slowing cognitive and motor decline in patients with dementia. No mediating effects between improvements in cognitive function via improved motor function were found. Future research into the underlying mechanistic associations is needed.