Background: Cancer-related fatigue (CRF) is one of the most troubling symptoms of cancer patients during chemotherapy, and no gold standard for the treatment of CRF has been established. Objective: This study aimed to examine the effects of the Baduanjin qigong on patients with colorectal cancer and CRF, and to explore its intervention effects. Methods: This was an open-label, randomized controlled clinical trial. Ninety patients with chemotherapy-treated colorectal cancer and CRF were randomized to a Baduanjin exercise group or a routine care group. The primary outcome was the Brief Fatigue Inventory (BFI) score at 24 weeks. The secondary outcomes were the Karnofsky Performance Status (KPS) and Pittsburgh Sleep Quality Index (PSQI) scores at 24 weeks. Results: There were no significant differences between the two groups in CRF level at baseline and 12 weeks. At 24 weeks, the proportion of patients with moderate-to-severe CRF was significantly smaller in the exercise group than in the control group (23.2 vs. 59.1%, p < 0.01). The KPS and PSQI scores were similar in the two groups at baseline and 12 weeks, but they were significantly higher and lower, respectively, at 24 weeks in the exercise group compared with the control group (KPS score: 89.3 ± 8.3 vs. 75.2 ± 11.5, p < 0.01; PSQI score: 4.1 ± 1.1 vs. 6.9 ± 2.0, p < 0.01). Significant time-group interactions were observed for all three scores (all p < 0.01). Conclusions: Baduanjin qigong exercise can relieve CRF in patients with colorectal cancer undergoing chemotherapy and can improve their physical activity level and their quality of sleep.