Aerobic training (AT) is a promising, non-pharmacological intervention to mitigate the deleterious effects of aging and disease on brain health. However, a large amount of variation exists in its efficacy. This is a secondary analysis of a randomized controlled trial of AT in 71 older adults with subcortical ischemic vascular cognitive impairment (NCT01027858). Specifically, we investigated: 1) whether sex moderates the relationship between AT and executive functions, and 2) the role of brain derived neurotrophic factor (BDNF) and gains in functional fitness capacity. Older adults were randomly assigned to either 6-month, thrice-weekly AT or to usual care plus education (CON). At baseline, trial completion, and 6-month follow-up, executive functions were assessed with the Trail Making Test (A & B), verbal digits forward and backward test, and the Stroop Test. Functional fitness capacity was assessed with the 6-Minute Walk Test. Compared with CON, AT significantly improved Trail Making Test performance in females but not males, an effect that was retained at follow-up. AT significantly increased BDNF levels in females but decreased levels in males. On the other hand, AT led to significant gains in functional fitness capacity in males only. This study provides evidence that sex differences exist in AT efficacy on brain health as well as in the biological mechanisms subserving AT.