Purpose <p>Long-term unemployment is accompanied by worse health, making it challenging to enter paid employment. This study aims to investigate effects of a health promotion program on physical and mental health, work ability, and entering paid employment among long-term non-employed individuals.</p> Methods <p>In a longitudinal study, Exercise Works participants (<i>N</i> = 208) and a treatment-as-usual group (<i>N</i> = 117) were followed with measurements at baseline, 3 months, and 12 months. The Exercise Works program is a health promotion program that lasts 12 to 18 weeks. It consists of individual- and group-based physical exercises, lifestyle education, and individual coaching for two half days per week. A generalized linear mixed model for repeated measurements was used to investigate changes within individuals in health status, employment participation, and work ability during the Exercise Works program in comparison to the control group. Subgroup analyses were performed based on socio-demographic characteristics and a per protocol analysis. Interviews with 20 participants and 21 professionals were conducted.</p> Results <p>This study demonstrated no significant improvements in physical and mental health, work ability and being in paid employment participation among participants of Exercise Works compared to the control group. Participants and professionals had a very positive impression of the Exercise Works program.</p> Conclusion <p>Despite the Exercise Works program being positively received, the effect evaluation did not demonstrate its effectiveness. Complex problems of non-employed persons should be addressed when developing a health promotion program.</p>