Introduction: Stroke survivors can experience various consequences that affect their physical and psychological balance. Yoga seems to be relevant for this population as it allows to work on both the body and the mind. The first objective of this study was to investigate the non-inferiority of yoga compared with conventional physical activity in improving physical function in patients with chronic post-stroke sequelae. The secondary objective was to investigate the superiority of yoga in improving the mental health of these patients. Methods: A randomized controlled trial was conducted. Thirty-six patients were randomized into two groups to practice a yoga program (YOG'AVC) or the Fitness and Mobility Exercise (FAME) program. Patients were assessed in a blinding mode pre- (T0) and post-program (T1) and 3–4 months after completion (T2). The physical assessments were the Berg Balance Scale, timed up and go test, 6-minute walk test, and quadriceps strength measured by hand-held dynamometer. Questionnaire assessments were: Activities-specific Balance Confidence Scale–Simplified, State-Trait Anxiety Inventory, Beck's Depression Inventory, and the Reintegration to Normal Living Index. Results: The YOG'AVC program was not inferior to the FAME program in improving balance, functional mobility and muscle strength. Both groups showed significant improvement (p < 0.05) between T0 and T1 in their anxiety, depression, and reintegration to normal life scores, with no significant difference between groups. Discussion: Both programs seem to be valuable in improving the physical abilities and psychological well-being of chronic post-stroke patients. However, further studies are required to confirm the difference between these programs.