Background. Declines in cognitive functioning are a normal part of aging that can affect daily functioning and quality of life. This study will examine the impact of an exercise training program, and a combined exercise and cognitive training program, on the cognitive and physical functioning of older adults. Methods/Design. Fit Bodies, Fine Minds is a randomized, controlled trial. Community-dwelling adults, aged between 65 and 75 years, are randomly allocated to one of three groups for 16 weeks. The exercise-only group do three 60-minute exercise sessions per week. The exercise and cognitive training group do two 60-minute exercise sessions and one 60-minute cognitive training session per week. A no-training control group is contacted every 4 weeks. Measures of cognitive functioning, physical fitness and psychological well-being are taken at baseline (0 weeks), post-test (16 weeks) and 6-month follop (40 weeks). Qualitative responses to the program are taken at post-test. Discussion. With an increasingly aged population, interventions to improve the functioning and quality of life of older adults are particularly important. Exercise training, either alone or in combination with cognitive training, may be an effective means of optimizing cognitive functioning in older adults. This study will add to the growing evidence base on the effectiveness of these interventions. Trial Registration. Australian Clinical Trials Register: ACTRN012607000151437.