Depression and fatigue have previously been suggested to share an underlying genetic contribution. The present study aims to investigate and characterize the familiality and genetic relationship between depression and fatigue. The familiality of depression and fatigue was assessed by calculating relative risks, measured by the prevalence ratio, within 643 monozygotic (MZ) and 577 dizygotic (DZ) twin pairs. Bivariate twin modeling was utilized to assess the magnitude of shared heritability between depression and fatigue. Finally, the relationship between depression and fatigue was investigated using the co-twin control method, to determine whether the association is explained by causal or non-causal models. We observed an increased risk of fatigue in co-twins of probands with depression and increased risk of depression in co-twins of probands with fatigue. Higher risks were observed in MZ compared to DZ twin pairs, and bivariate heritability analyses indicated significant genetic components for depression and fatigue, with heritability estimates of 48% and 41%, respectively. Importantly, a significant additive genetic correlation of 0.71 [95% CI = 0.51–0.92) and bivariate heritability of 21% [95% CI = 10–35%] was observed between depression and fatigue. Furthermore, results from the co-twin control method indicate a non-causal genetic relationship that likely explains the association between depression and fatigue. Notably, the contribution of shared genetic factors remained significant, independent of the overlapping symptoms, indicating that the relationship between co-occurring depression and fatigue is primarily due to shared genetic factors rather than overlapping symptomatology.