Objective: The purpose of this study was to examine course and predictors of fatigue in military personnel deployed to Afghanistan. Methods: A total of 906 soldiers in the Dutch Armed Forces who participated in a 4-month mission to Afghanistan were included in this study. Assessment took place prior to and 1, 6, 12, and 24 months after deployment. Data were collected between 2005 and 2011. The fatigue severity subscale of the Checklist Individual Strength was used to indicate the level of fatigue during the previous 2 weeks. Mixed models and logistic regression analysis were used to predict course and prevalence of fatigue after deployment. Predictors of postdeployment fatigue were assessed prior to deployment. Results: The mean level of fatigue increased significantly following deployment (B = 0.58, P = .007). In total, 274 soldiers (30.2%) were severely fatigued at least once after deployment and 130 (14.3%) soldiers had recurrent levels of severe fatigue. Only a minority of the veterans with severe fatigue could be classified as having posttraumatic stress disorder (PTSD, per DSM-IV-TR criteria) or potential medical problems. Significant predeployment predictors of less favorable courses of fatigue after deployment were higher levels of fatigue (B = 0.46, P ≤ .001), emotional abuse during childhood (B = 0.99, P ≤ .001), and harm avoidance (B = 0.27, P = .012). These predeployment factors also predicted severe fatigue after deployment. Conclusions: Severe fatigue is a substantial problem in Afghanistan War veterans that does not seem to resolve over time. In a majority of cases, the symptoms cannot be attributed to medical problems or PTSD, whereas predeployment differences in psychosocial factors partially explain course and prevalence of postdeployment fatigue. These findings support assumptions that a complex interplay of various factors might be responsible for the symptoms.