Aging is the major risk factor for neurodegenerative diseases such as Alzheimer's disease, but little is known about the processes that lead to age-related decline of brain structures and function. Here we use RNA-seq in combination with high resolution histological analyses to show that aging leads to a significant deterioration of neurovascular structures including basement membrane reduction, pericyte loss, and astrocyte dysfunction. Neurovascular decline was sufficient to cause vascular leakage and correlated strongly with an increase in neuroinflammation including up-regulation of complement component C1QA in microglia/monocytes. Importantly, long-term aerobic exercise from midlife to old age prevented this age-related neurovascular decline, reduced C1QA+ microglia/monocytes, and increased synaptic plasticity and overall behavioral capabilities of aged mice. Concomitant with age-related neurovascular decline and complement activation, astrocytic Apoe dramatically decreased in aged mice, a decrease that was prevented by exercise. Given the role of APOE in maintaining the neurovascular unit and as an anti-inflammatory molecule, this suggests a possible link between astrocytic Apoe, age-related neurovascular dysfunction and microglia/monocyte activation. To test this, Apoe-deficient mice were exercised from midlife to old age and in contrast to wild-type (Apoe-sufficient) mice, exercise had little to no effect on age-related neurovascular decline or microglia/monocyte activation in the absence of APOE. Collectively, our data shows that neurovascular structures decline with age, a process that we propose to be intimately linked to complement activation in microglia/monocytes. Exercise prevents these changes, but not in the absence of APOE, opening up new avenues for understanding the complex interactions between neurovascular and neuroinflammatory responses in aging and neurodegenerative diseases such as Alzheimer’s disease.