Background: A physically active lifestyle has the potential to prevent cognitive decline and dementia, yet the optimal type of physical activity/exercise remains unclear. Dance is of special interest as it complex sensorimotor rhythmic activity with additional cognitive, social, and affective dimensions. Objectives: To determine whether dance benefits executive function more than walking, an activity that is simple and functional. Methods: Two-arm randomized controlled trial among community-dwelling older adults. The intervention group received 1 h of ballroom dancing twice weekly over 8 months (~69 sessions) in local community dance studios. The control group received a combination of a home walking program with a pedometer and optional biweekly group-based walking in local community park to facilitate socialization. Main outcomes: Executive function tests: processing speed and task shift by the Trail Making Tests, response inhibition by the Stroop Color-Word Test, working memory by the Digit Span Backwards test, immediate and delayed verbal recall by the Rey Auditory Verbal Learning Test, and visuospatial recall by the Brief Visuospatial Memory Test (BVST). Results: One hundred and fifteen adults (mean 69.5 years, SD 6.4) completed baseline and delayed baseline (3 weeks apart) before being randomized to either dance (n = 60) or walking (n = 55). Of those randomized, 79 (68%) completed the follow-up measurements (32 weeks from baseline). In the dance group only, "non-completers" had significantly lower baseline scores on all executive function tests than those who completed the full program. Intention-to-treat analyses showed no group effect. In a random effects model including participants who completed all measurements, adjusted for baseline score and covariates (age, education, estimated verbal intelligence, and community), a between-group effect in favor of dance was noted only for BVST total learning (Cohen's D Effect size 0.29, p = 0.07) and delayed recall (Cohen's D Effect size = 0.34, p = 0.06). Conclusion: The superior potential of dance over walking on executive functions of cognitively healthy and active older adults was not supported. Dance improved one of the cognitive domains (spatial memory) important for learning dance. Controlled trials targeting inactive older adults and of a higher dose may produce stronger effects, particularly for novice dancers.