This randomized controlled trial (NCT03475316) examined the relative efficacy of 6 months of social ballroom dancing and treadmill walking on a composite executive function score, generated from digit symbol substitution test, flanker interference, and walking while talking tasks. Brain activation during functional magnetic resonance imaging (fMRI) versions of these executive function tasks were secondary outcomes. Twenty-five dementia-at-risk older adults (memory impairment screen score of ≥3 to ≤6 and/or an Alzheimer’s disease-8 Dementia Screening Interview of ≥1) were randomized in June 2019 to March 2020—16 completed the intervention before study termination due to the COVID-19 (eight in each group). Composite executive function scores improved post-intervention in both groups, but there was no evidence for between-group differences. Social dancing, however, generated greater improvements on digit symbol substitution test than treadmill walking. No intervention-related differences were observed in brain activation—although less hippocampal atrophy (tertiary) was observed following social dancing than treadmill walking. These preliminary findings are promising but need to be confirmed in future large-scale and sufficiently powered randomized controlled trials.