Objectives The present study evaluated the efficacy of an exercise intervention to reduce work-related fatigue (emotional exhaustion, overall fatigue, and need for recovery). The effects of exercise on self-efficacy, sleep, work ability, cognitive functioning and aerobic fitness (secondary outcomes) were also investigated. Methods Employees with high levels of work-related fatigue were randomly assigned to either a 6-week exercise intervention (EI; N=49) or a wait-list control group (WLC; N=47). All participants were measured pre- (T0) and post-intervention (T1). EI participants were also measured 6 (T2) and 12 weeks (T3) after the end of the intervention. Analyses were based on intention-to-treat (ITT) and per-protocol (PP). PP analyses only included EI participants (N=31) who completed the intervention and WLC participants (N= 35) who did not increase their exercise level during the wait period. Results Analyses of covariance (ANCOVA) revealed that, at T1, the EI group reported lower emotional exhaustion and overall fatigue than the WLC group, however, only according to PP analyses. Both according to ITT and PP analyses, EI participants showed higher sleep quality, work ability, and self-reported cognitive functioning at T1 compared to WLC participants. Intervention effects were maintained at T2 and T3. Conclusions The exercise intervention had enduring effects on work-related fatigue and broader indicators of employee well-being. This study demonstrates that, in case of work-related fatigue, exercise does constitute a powerful medicine for those who comply with the treatment.