Physical exercise, particularly aerobic exercise, is documented as providing a low cost regimen to counter well-documented cognitive declines including memory, executive function, visuospatial skills, and processing speed in normally aging adults. Prior aging studies focused largely on the effects of medium to long term (>6 months) exercise training; however, the shorter term effects have not been studied. In the present study, we examined changes in brain blood flow, cognition, and fitness in 37 cognitively healthy sedentary adults (57–75 years of age) who were randomized into physical training or a wait-list control group. The physical training group received supervised aerobic exercise for 3 sessions per week 1 h each for 12 weeks. Participants’ cognitive, cardiovascular fitness and resting cerebral blood flow (CBF) were assessed at baseline (T1), mid (T2), and post-training (T3). We found higher resting CBF in the anterior cingulate region in the physical training group as compared to the control group from T1 to T3. Cognitive gains were manifested in the exercise group’s improved immediate and delayed memory performance from T1 to T3 which also showed a significant positive association with increases in both left and right hippocampal CBF identified earlier in the time course at T2. Additionally, the two cardiovascular parameters, VO2 max and rating of perceived exertion (RPE) showed gains, compared to the control group. These data suggest that even shorter term aerobic exercise can facilitate neuroplasticity to reduce both the biological and cognitive consequences of aging to benefit brain health in sedentary adults.