Background: Fishery is a hazardous occupation and fatigue may contribute to the observed risks. This study aims to investigate the association between workload and fatigue among Danish fishermen. Materials and methods: The cross-sectional survey of demographic characteristics and self-reported exposure and health data was performed on a random sample of 270 active fishermen. We applied the validated Multidimensional Fatigue Inventory (MFI-20) to assess the degrees of the different dimensions of perceived fatigue. We estimated physical workload using questions regarding the frequency of seven physical work activities and analysed the association between fatigue and workload using multiple linear regressions. Results: The mean fatigue scores were 9.18 (SD 3.58) for general fatigue, 9.05 (SD 3.36) for physical fatigue, 7.57 (SD 3.03) for reduced activity and 7.16 (SD 3.07) for mental fatigue. Highest levels of fatigue were observed among fishermen at Danish seiners (mean 10.21), and fatigue scores decreased with more days at sea. However, none of these results were significant. Adjusted analyses showed that physical workload was significantly related to general fatigue (b = 0.20, 95% CI: 0.12–0.28), physical fatigue (b = 0.10, 95% CI: 0.04–0.16) and mental fatigue (b = 0.09, 95% CI: 0.01–0.16). Reduced activity was unrelated to work exposures. Conclusions: General fatigue was the dominant fatigue dimension among Danish fishermen and it is mostly associated with physical workload. Physical workload was additionally significantly associated to the levels of physical and mental fatigue. Fishermen had a lower average score for all fatigue dimensions compared to those seen in general Danish working population. Prospective studies are required to assess whether the identified associations are causal.