Objective: To investigate whether 12 weeks of graded exercise with pacing would improve specific physiological, psychological and cognitive functions in people with chronic fatigue syndrome (CFS). Design: Randomised controlled trial. Setting: Human performance laboratory at the University of Western Australia. Participants: 61 patients aged between 16 and 74 years diagnosed with CFS. Interventions: Either graded exercise with pacing (32 patients) or relaxation/flexibility therapy (29 patients) performed twice a day over 12 weeks. Main outcome measures: Changes in any of the physiological, psychological or cognitive variables assessed. Results: Following the graded exercise intervention, scores were improved for resting systolic blood pressure (P=0.018), work capacity (W.kg(-1)) (P=0.019), net blood lactate production (P=0.036), depression (P=0.027) and performance on a modified Stroop Colour Word test (P=0.029). Rating of perceived exertion scores, associated with an exercise test, was lower after graded exercise (P=0.013). No such changes were observed in the relaxation/flexibility condition, which served as an attention-placebo control. Conclusions: Graded exercise was associated with improvements in physical work capacity, as well as in specific psychological and cognitive variables. Improvements may be associated with the abandonment of avoidance behaviours.