Background: Dementia is associated with cognitive and functional deficits, and poses a significant personal, societal, and economic burden. Directing interventions towards older adults with self-reported cognitive complaints may provide the greatest impact on dementia incidence and prevalence. Risk factors for cognitive and functional deficits are multifactorial in nature; many are cardiovascular disease risk factors and are lifestyle-mediated. Evidence suggests that multiple-modality exercise programs can provide cognitive and functional benefits that extend beyond what can be achieved from cognitive, aerobic, or resistance training alone, and preliminary evidence suggests that novel mind-motor interventions (i.e., Square Stepping Exercise; SSE) can benefit cognition and functional fitness. Nevertheless, it remains unclear whether multiple-modality exercise combined with mind-motor interventions can benefit diverse cognitive and functional outcomes in older adults with cognitive complaints. Methods/Design: The Multiple-Modality, Mind-Motor (M4) study is a randomized controlled trial investigating the cognitive and functional impact of combined physical and cognitive training among community-dwelling adults with self-reported cognitive complaints who are 55 years of age or older. Participants are randomized to a Multiple-Modality and Mind-Motor (M4) intervention group or a Multiple-Modality (M2) comparison group. Participants exercise for 60 minutes/day, 3-days/week for 24 weeks and are assessed at baseline, 24 weeks and 52 weeks. The primary outcome is global cognitive function at 24 weeks, derived from the Cambridge Brain Sciences computerized cognitive battery. Secondary outcomes are: i) global cognitive function at 52 weeks; ii) domain-specific cognitive function at 24 and 52 weeks; iii) mobility (gait characteristics under single and dual-task conditions and balance); and 3) vascular health (blood pressure and carotid arterial measurements). We will analyze data based on an intent-to-treat approach, using mixed models for repeated measurements. Discussion: The design features of the M4 trial and the methods included to address previous limitations within cognitive and exercise research will be discussed. Results from the M4 trial will provide evidence of combined multiple-modality and cognitive training among older adults with self-reported cognitive complaints on cognitive, mobility-related and vascular outcomes.