Fatigue is one of the most common symptoms following traumatic brain injury (TBI). Despite its prevalence, fatigue remains a challenging concept to define and measure. The aim of the present study was to explore potential relationships between self-rated fatigue in patients with TBI and performance on several widely used neuropsychological tests. In a cross-sectional design, patients with TBI (n = 68) and healthy controls (n = 27) underwent a comprehensive battery of commonly used neuropsychological tests and completed two self-assessment fatigue scales, the Fatigue Severity Scale and the Mental Fatigue Scale. Patients with TBI performed worse on neuropsychological tests of short-term memory, processing speed and executive functioning (inhibition) compared to healthy controls. Within the TBI group, only the Paced Auditory Serial Addition Test (PASAT) and the Stroop-Inhibition task showed significant correlations with measures of fatigue. However, after adjusting for relevant demographic variables, including age, gender, education and TBI severity, only PASAT remained significantly associated with the Mental Fatigue Scale (r = .45, p = .005). Within the healthy control group, no such associations were found. These results highlight an interesting relationship between PASAT performance and self-assessed fatigue. With further research, PASAT, modifications of it or similar measures could potentially help clinicians in evaluating fatigue in patients with TBI.