In the stroke population, regular physical activity has the potential to positively influence both stroke-related outcomes and risk factors for recurrent events. The overall objective of this work was to determine the feasibility and effects of exercise testing and early aerobic training in the sub-acute stroke population. The feasibility of maximal exercise testing on a semi-recumbent cycle ergometer was established, and recommendations were provided for test termination and criteria for maximal effort during exercise testing. Individuals with stroke who participated in an early aerobic exercise program on a semi-recumbent cycle ergometer in addition to conventional rehabilitation demonstrated significant improvement in VO2peak and a trend towards greater improvement in peak work rate and functional ambulation, compared to those who received conventional rehabilitation only. Results contribute to our knowledge about the influence of physical activity among stroke survivors, and have implications on shaping the clinical practice in stroke rehabilitation.