The purpose of this randomized, controlled clinical trial was to preliminarily examine the effects of a three-week walking exercise program (WEP) on fatigue-related experiences of acute myelogenous leukemia (AML) patients receiving chemotherapy. Eligible AML patients were randomly assigned to either an experimental group (n = 11), which received 12 minutes of WEP per day, five days per week for three consecutive weeks, or to a control group (n = 11), which received standard ward care. Effects of the WEP were assessed by seven indicators: worst and average fatigue intensities, fatigue interference with patients' daily life, 12-minute walking distance, overall symptom distress, anxiety, and depressive status. All patients were evaluated four times: before chemotherapy (baseline or Day 1), Day 7, Day 14, and Day 21 of chemotherapy. Data were analyzed by Generalized Estimating Equation and revealed that AML patients in the three-week WEP group had a significantly greater increase in 12-minute walking distance than the control group. Patients in the WEP also had lower levels of fatigue intensity and interference, symptom distress, anxiety, and depressive status than the control group. Although preliminary, our results strongly suggest that three weeks of systematic walking exercise is clinically feasible for AML patients undergoing chemotherapy and can effectively improve their fatigue-related experiences.