Physical activity upregulates endothelial nitric oxide synthase (eNOS), improves endothelium function, and protects from vascular disease. Here, we tested whether voluntary running would enhance neovascularization and long-term recovery following mild brain ischemia. Wild-type mice were exposed to 30 minutes of middle-cerebral artery occlusion (MCAo) and reperfusion. Continuous voluntary running on wheels conferred long-term upregulation of eNOS in the vasculature and of endothelial progenitor cells (EPCs) in the spleen and bone marrow (BM). This was associated with higher numbers of circulating EPCs in the blood and enhanced neovascularization. Moreover, engraftment of TIE2/LacZ-positive BM-derived cells was increased in the ischemic brain. Four weeks after the insult, trained animals showed higher numbers of newly generated cells in vascular sites, increased density of perfused microvessels and sustained augmentation of cerebral blood flow within the ischemic striatum. Moreover, running conferred tissue sparing and improved functional outcome at 4 weeks. The protective effects of running on angiogenesis and outcome were completely abolished when animals were treated with a NOS inhibitor or the antiangiogenic compound endostatin after brain ischemia, and in animals lacking eNOS expression. Voluntary physical activity improves long-term stroke outcome by eNOS-dependent mechanisms related to improved angiogenesis and cerebral blood flow.