Background: Cancer-related fatigue (CRF) reduces quality of life and the activity level of patients with cancer. Cancer related fatigue can be reduced by exercise interventions that may concurrently increase muscle mass. We hypothesized that low muscle mass is directly related to higher CRF. Methods: A total of 233 patients with advanced cancer starting palliative chemotherapy for lung, colorectal, breast, or prostate cancer were studied. The skeletal muscle index (SMI) was calculated as the patient's muscle mass on level L3 or T4 of a computed tomography scan, adjusted for height. Fatigue was assessed with the Functional Assessment of Chronic Illness Therapy-fatigue questionnaire (cut-off for fatigue <34). Multiple linear regression analyses were conducted to study the association between SMI and CRF adjusting for relevant confounders. Results: In this group of patients with advanced cancer, the median fatigue score was 36 (interquartile range 26–44). A higher SMI on level L3 was significantly associated with less CRF for men (B 0.447, P 0.004) but not for women (B − 0.401, P 0.090). No association between SMI on level T4 and the Functional Assessment of Chronic Illness Therapy-fatigue score was found (n = 82). Conclusions: The association between SMI and CRF may lead to the suggestion that male patients may be able to reduce fatigue by exercise interventions aiming at an increased muscle mass. In women with advanced cancer, CRF is more influenced by other causes, because it is not significantly related to muscle mass. To further reduce CRF in both men and women with cancer, multifactorial assessments need to be performed in order to develop effective treatment strategies.