The brain's vasculature is likely to be subjected to the same age-related physiological and anatomical changes affecting the rest of the cardiovascular system. Since aerobic fitness is known to alleviate both cognitive and volumetric losses in the brain, it is important to investigate some of the possible mechanisms underlying these beneficial changes. Here we investigated the role that estimated cardiorespiratory fitness (eCRF) plays in determining the relationship between aging and cerebral blood flow (CBF) in a group of older adults (ages 55–85). Using arterial spin labeling to quantify CBF, we found that blood flow in the gray matter was positively correlated with eCRF and negatively correlated with age. Subsequent analyses revealed that eCRF fully mediated the effects of age on CBF in the gray matter, but not in the white matter. Additionally, regional measures of CBF were related to regional measures of brain volume. These findings provide evidence that age-related effects on cerebrovascular health and perfusion in older adults are largely influenced by their eCRF levels.