Stress-related exhaustion has been linked to a pattern of selective cognitive impairments, mainly affecting executive functioning, attention and episodic memory. Little is known about potential treatments of these cognitive deficits. The purpose of this study was to evaluate the effects of a process-based cognitive training intervention, designed to target the specific cognitive impairments associated with stress-related exhaustion. To this end, patients diagnosed with exhaustion disorder (ED) were randomized to either a multimodal stress rehabilitation program with the addition of a process-based cognitive training intervention (training group, n = 27) or a treatment-as-usual control condition, consisting of multimodal stress rehabilitation with no additional training (control group, n = 32). Treatment effects were evaluated through an extensive cognitive test battery, assessing both near and far transfer effects, as well as self-report forms regarding subjective cognitive complaints and burnout levels. Results showed pronounced training-related improvements on the criterion updating task (p < 0.001). Further, evidence was found of selective near transfer effects to updating (p = 0.01) and episodic memory (p = 0.04). Also, the trained group reported less subjective memory complaints (p = 0.02) and levels of burnout decreased for both groups, but more so for the trained group (p = 0.04), following the intervention. These findings suggest that process-based cognitive training may be a viable method to address the cognitive impairments associated with ED.