Because of the serious adverse consequences of unexplained fatigue, it is important to identify factors that determine the prognosis of unexplained fatigue and the onset of long-term sickness absence in fatigued employees. Analyses were based on the Maastricht Cohort Study, a prospective population-based cohort study among more than 12,000 employees. Severely fatigued employees who were not on sick leave (n = 2108) were selected at baseline and followed up at six time points during the course of 2 years. Point prevalences of severe fatigue (59% to 63%) and long-term sickness absence (1.8% to 3.1%) among participants were fairly stable at all consecutive time points. Lower levels of fatigue severity, work-related exhaustion and anxious mood, absence of conflicts with colleagues, and good self-rated health at baseline were predictors of the onset of recovery from fatigue in survival analyses. Older age, low decision authority, female sex, working in nightshift, a physical attribution of fatigue, and a history of absenteeism were predictors of the onset of long-term absenteeism. The course of unexplained fatigue in employees is characterized by remission and relapse in time while the absolute risk of long-term absenteeism is small. Given the broad range of predictors, it appears that fatigue and long-term sickness absence entangle different underlying processes. Our findings underscore the notion that prevention and treatment of fatigue should be aimed at health perception and emotional well-being.