Background: Post-stroke fatigue is a common symptom after stroke. However, studies on the factors associated with early and late fatigue are scarce. The objective of this study was to identify variables associated with early and late fatigue. Methods: In the German Stroke Cohort Augsburg (SCHANA) study, participants were interviewed during their hospital stay and completed a postal questionnaire 3 and 12 months post-stroke. Fatigue was assessed using the Fatigue Assessement Scale (FAS). In addition, depression was measured by the Patient Health Questionnaire (PHQ-9), general health status by the EQ-5D visual analog scale, and physical activity by the International Physical Activity Questionnaire (IPAQ). Multivariable regression models were used to determine the associations between FAS scores at 3 and 12 months post-stroke and demographic, psychosocial and health-related covariables. Results: Among 505 participants, the frequency of fatigue was 31.1% 3 months and 29.1% 12 months post-stroke. Prior stroke (ß = 2.37, p = 0.0076), prior diagnosis of depression (ß = 5.04, p = 0.0001), higher NIHSS (ß = 0.25, p = 0.0360) and higher PHQ-9 scores (ß = 0.55, p < 0.0001) were significantly associated with higher fatigue levels 3 months post-stroke. Additionally, younger age (ß = −0.07, p = 0.0219), a worse rating of general health at baseline (ß = −0.04, p = 0.0287) and low pre-stroke physical activity (ß = −0.0004, p = 0.0089) were significantly associated with higher fatigue levels 12 months after stroke. Conclusions: Fatigue is a common and persisting symptom even in patients with mild impairment. Prior depressive disorder and early depressive symptoms were the most relevant predictors of both early and late fatigue.