Objectives: To investigate the short-term and long-term effectiveness of two, brief, preventive, work stress management programmes. One programme was a cognition-focused programme, the other was a newly developed intervention in which physical exercise and relaxation were combined. It was hypothesised that the newly developed intervention would be more effective in reducing psychological complaints than the cognitive intervention. Both programmes consisted of four sessions in a period of 10 weeks. Methods: From a working population engaged in a periodic health check-up, employees above a minimum stress level (n = 396) were invited to participate in a randomised comparative outcome study with pre-trial, post-trial and 6-month follow-up measures. After giving informed consent 130 participants entered the study (response rate 33%). Outcome measures consisted of three self-reported questionnaires on psychological complaints. Results: It was found that both interventions revealed a positive impact on psychological complaints, burnout and fatigue, both at short-term and at 6-month follow-up. No statistical interaction effects between the two interventions were found. Calculation of the clinical significance of the effects indicated that 50% of the employees with psychological complaints who participated in the physical intervention and 60% of the employees who participated in the cognitive intervention improved and returned to functioning within normal range both in the short term and in the long term at 6 months. Conclusion: The data indicate that interventions were equally effective on psychological complaints, burnout and fatigue. © Springer-Verlag 2005.