Chronic cancer-related fatigue in otherwise asymptomatic post-allogeneic hematopoietic stem cell transplant (HSCT) patients is common and debilitating. This pilot study investigated whether patients with no clinical or psychological abnormalities but severe fatigue would respond to an individually adapted aerobic exercise program. Participants were 12 patients (eight male, and four female patients), median age 47 years and 41 months post-HSCT with a variety of hematopoetic cancer diagnoses. All underwent a 12-week individualized mild aerobic exercise program, preceded by a 4-week introduction and baseline testing phase. Psychological measures included fatigue, mood and depression. Exercise-related physiological outcomes included power output at ventilatory threshold 2 (VT2) and associated changes in stroke volume, heart rate, blood lactate concentration and ratings of perceived exertion. Patients were assessed for fatigue before, immediately after and at 3, 6, 9 and 12 months post-program. Significant improvements were found on both measures of fatigue (both P<0.001), with a very large effect size of 1.82 on the The Functional Assessment of Cancer Therapy - Fatigue Module, which were maintained over the follow-up period. Exercise testing revealed a mean increase (P<0.001) of 28% in power output at VT2 with an increase (P<0.001) in stroke volume and a decrease (P<0.001) in heart rate, blood lactate and perceived exertion at pre-intervention VT2 power output.