Physical exercise is suggested to enhance cognition in older individuals, however, evidence from randomized controlled trials (RCTs) is scarce. We thus carried out an RCT on 93 healthy older participants to evaluate the impact of an 8-week online-based physical activity intervention on cognitive functions. Participants were randomly assigned to 8 weeks of online interventions of either multicomponent physical activity focusing on aerobic but including coordination and balance exercises, or active control comprising relaxation and podcasts on aging topics. The primary outcome was the change in parameter visual processing speed C, derived from a TVA-based whole report task. VO₂max and various neuropsychological test scores were additionally assessed. Although significant VO₂max gain was only found for the physical activity group, we did not find a significant group x time point interaction indicating gains compared to the control group. Similarly, although only the physical exercise group showed enhanced visual processing speed C, the interaction was not significant. Significant group x time point interactions for visual memory and executive functioning indicated higher gains in the physical exercise group for these functions. Visual memory gain was furthermore related to VO₂max gain in the physical exercise group. We assume that the lack of VO₂max gain differences between groups was due to already above-average scores at baseline, limiting “room for improvement”. Nevertheless, the study results imply that an increase in physical fitness leads to the enhancement of attentional, memory, and executive functions in the elderly.