Stroke often aggravated age-related cognitive impairments that strongly affect several aspects of quality of life. However, few studies are, to date, focused on rehabilitation strategies that could improve cognition. Among possible interventions, aerobic training is well known to enhance cardiovascular and motor functions but may also induce beneficial effects on cognitive functions. To assess the effectiveness of aerobic training on cognition, it seems necessary to know whether training promotes the neuroplasticity in brain areas involved in cognitive functions. In the present review, we first explore in both human and animal how aerobic training could improve cognition after stroke by highlighting the neuroplasticity mechanisms. Then, we address the potential effect of combinations between aerobic training with other interventions, including resistance exercises and pharmacological treatments. In addition, we postulate that classic recommendations for aerobic training need to be reconsidered to target both cognition and motor recovery because the current guidelines are only focused on cardiovascular and motor recovery. Finally, methodological limitations of training programs and cognitive function assessment are also developed in this review to clarify their effectiveness in stroke patients.