Patients who seek medical care for stress-related mental health problems frequently report cognitive impairments as the most pronounced symptom. The purpose of the present study was to compare cognitive function in patients with stress-related exhaustion with that in healthy controls, using a comprehensive battery of cognitive tests. We also explored whether neuropsychological findings were related to severity of illness measured using the Shirom-Melamed burnout questionnaire and hospital anxiety and depression scale. Thirty-three patients (15 males) and 37 healthy controls (11 males), mean age 46 years [standard deviation (SD) 3.9] and 47 years (SD 4.3), respectively, were included in the final analysis. Five cognitive domains were assessed: (1) speed, attention and working memory, (2) learning and episodic memory, (3) executive functions, (4) visuospatial functions and (5) language. The most pronounced difference between patients and controls was seen on executive function, when tested with a multidimensional test, including aspects of speed, control and working memory. The patients also performed poorer on Digit span, measuring attention span and working memory as well as on learning and episodic memory, when measured as delayed recall and the difference between immediate and delayed recall. Delayed recall was the only test that was significantly related to severity of burnout symptoms among the patients. This could reflect poor cognitive sustainability in the patients with the highest burnout scores, as this particular test was the last one performed during the test session. This study clearly shows that cognitive impairment should be considered when evaluating and treating patients who seek medical care for stress-related exhaustion.