Background: Health-related quality of life (HRQoL) is an important health outcome in older adults. This study aimed to assess the efficacy of the ProBalance rehabilitation programme on HRQoL of community-dwelling older adults with balance impairments and to investigate whether effects differ between age groups and/or HRQoL components. Methods: A single-blind, randomised controlled trial included community-dwelling older adults, aged 65–85, with balance impairments. Participants (n = 52) were randomly allocated to an intervention group (IG) or a control group (CG). A rehabilitation programme included gait, balance, functional training, strengthening, flexibility, and 3D training. A group-based intervention was administered over a period of 12 weeks (90-min sessions, 2 days per week). A wait-list control group was instructed to maintain their usual activities during the same period. Participants' HRQoL was assessed using the SF-36 questionnaire. The time points for assessment were at zero (pre-test), 12 (post-test), and 24 weeks (follow up). Results: A trend for higher HRQoL in the IG compared to the CG and a significant interaction of group with time were found, with significantly higher increases in HRQoL from the pre-test to the post-test (and to follow-up) in the IG, compared to the CG. Results were independent of age group (young-old vs. old-old) and HRQoL component (physical vs. mental). Conclusions: Present results suggest that the ProBalance programme had a beneficial effect on HRQoL of community-dwelling older adults, which held across young and old adults and not only comprised physical but also mental HRQoL.