Objectives: Complaints of prolonged fatigue are considered as a major health problem, as it can affect daily functioning and may lead to work disability. To increase knowledge about the effectiveness of interventions focussing on fatigued patients, a study was designed to evaluate an established training programme for patients with prolonged fatigue. Materials and Methods: Eighteen patients who reported fatigue to be one of their major health complaints and who were suffering from functional impairments attended a training programme of six weeks, three times a week. The training consisted mainly of physical endurance training, relaxation therapy and breathing exercises in rest. At baseline, time- and frequency-domain measures of heart rate variability (HRV) and respiration rate measurements were recorded during rest and during recovery after bicycle exercise. Furthermore, fatigue complaints were assessed with the Checklist Individual Strength (CIS). These measurements were repeated at three weeks and six weeks from baseline. Results: After three weeks, HRV increased significantly in rest - SDNN, i.e. standard deviation of normal beat-to-beat intervals (p = 0.02), very low frequency (p = 0.04) and low frequency (p = 0.04) - and showed a positive trend in the remaining HRV components. No significant HRV changes during recovery were found. Respiration rate decreased significantly after six weeks during rest (from 11.8, SD = 4.65 to 8.1, SD = 2.57 b×min-1) and during recovery (from 15.1, SD = 4.90 to 10.4, SD = 2.97 b×min-1). In all patients, CIS scores decreased after six weeks training (from 106, SD = 13.3 to 78, SD = 21.8, p = 0.001). Conclusions: The results suggest that a six-week training programme has a beneficial effect on physiological and subjective parameters in patients with severe complaints of fatigue.