The effects of a structured exercise program on the cognitive functioning of 84 clinically depressed middle-aged and older adults (mean age = 57 years) were examined. Participants were randomized to either 4 months of aerobic exercise (n = 42) or antidepressant medication (n = 42). Assessments of cognitive functioning (memory, psychomotor speed, executive functioning, and attention/concentration), depression, and physical fitness (aerobic capacity and exercise endurance) were conducted before and after the intervention. Exercise-related changes (accounting for baseline levels of cognitive functioning and depression) were observed for memory (p = .01) and executive functioning (p = .03). There were no treatment-group differences on tasks measuring either attention/concentration or psychomotor speed. Results indicate that exercise can exert influence on specific areas of cognitive functioning among depressed older adults. Further research is necessary to clarify the kinds of cognitive processes that are affected by exercise and the mechanisms by which exercise affects cognitive functioning.