Stress-related exhaustion has been associated with selective and enduring cognitive impairments. However, little is known about how to address cognitive deficits in stress rehabilitation and how this influences stress recovery over time. The aim of this open-label, parallel randomized controlled trial (ClinicalTrials.gov: NCT03073772) was to investigate the long-term effects of 12 weeks cognitive or aerobic training on cognitive function, psychological health, and work ability for patients diagnosed with exhaustion disorder (ED). One-hundred-and-thirty-two patients (111 women) participating in multimodal stress rehabilitation were randomized to receive additional cognitive training (n = 44), additional aerobic training (n = 47), or no additional training (n = 41). Treatment effects were assessed before, immediately after and one-year post intervention. The primary outcome was global cognitive function. Secondary outcomes included domain-specific cognition, self-reported burnout, depression, anxiety, fatigue and work ability, aerobic capacity, and sick-leave levels. Intention-to-treat analysis revealed a small but lasting improvement in global cognitive functioning for the cognitive training group, paralleled by a large improvement on a trained updating task. The aerobic training group showed improvements in aerobic capacity and episodic memory immediately after training, but no long-term benefits. General improvements in psychological health and work ability were observed, with no difference between interventional groups. Our findings suggest that cognitive training may be a viable method to address cognitive impairments for patients with ED, whereas the effects of aerobic exercise on cognition may be more limited when performed during a restricted time period. The implications for clinical practice in supporting patients with ED to adhere to treatment are discussed.