Stroke commonly leads to reduced mobility, which leads to deconditioning and a worsening of vascular risk factors, such as diabetes. The worsened risk profile leads to further strokes and disability--a vicious cycle for the stroke survivor. Exercise (walking) therapy may break this cycle by providing adequate stimuli for improving gait through plastic adaptation in the brain and through increasing fitness. Randomized, controlled data demonstrate the efficacy for gains in fitness and walking speed, the latter being related to lasting changes in activation patterns of the brainstem and cerebellum. Diabetes and muscle inflammation can also be improved by aerobic exercise training. The scope of this review summarizes these data and identifies unresolved issues related to optimization, intensity and maintenance of therapy effects. Exercise should be an integral part of every rehabilitation program.