Context Physical exercise can alleviate cancer-related fatigue. Randomized controlled trials in patients with advanced cancer are scarce. Objectives We test the impact of a structured, individual sports program on fatigue in patients with advanced cancer. Methods Seventy-seven patients were invited to participate in this randomized controlled trial exploring the effects of physical exercises on fatigue 12 and 24 weeks after baseline. Patients were randomized into three groups. Group A received treatment as usual, Group B was taught a structured, individual sports program, and Group C received additional ambulatory physiotherapeutical supervision. Primary outcome was general fatigue, secondary outcomes included rate of severe general fatigue, further dimensions of the Multidimensional Fatigue Inventory (MFI), as well as walking distance. Results Mean score of general fatigue as well as other MFI subdimensions differed nonsignificantly between all groups at 12 weeks. However, the mental fatigue score demonstrated a statistically significant difference between the three groups. The rate of severe general fatigue was significantly reduced within Intervention Group C. Significant longitudinal change of MFI-dimension mental fatigue was found and reached the threshold for minimal clinically important difference, while all MFI-dimensions increased in Group A. Conclusion Our results imply that tumor-patients' severe general fatigue can be reduced when patients conduct appropriate physical exercise. This study amends previous knowledge, as it describes the impact of outpatient physical exercise on fatigue in a heterogeneous patient cohort with various advanced cancer entities. Furthermore, this trial differentiates between patients with only a self-directed exercise program versus those receiving additional partially professional supervision.