The aim of the present study was to evaluate the outcome of a behavioral medicine (BM) rehabilitation program and the outcome of its two main components, compared to a ‘treatment-as-usual’ control group (CG). The study employed a 4×4 repeated-measures design with four groups and four assessment periods (pre-treatment, post-treatment, 6-month follow-up, and 18-month follow-up). The group studied consisted of subjects on sick leave identified in a nationwide health insurance scheme in Sweden. After inclusion, the subjects were randomized to one of four conditions, which were: (1) behavior-oriented physical therapy (PT); (2) cognitive behavioral therapy (CBT); (3) BM rehabilitation consisting of PT+CBT (BM); (4) a ‘treatment-as-usual’ CG. The treatments were given over a period of 4 weeks, PT and CBT on a part-time basis and BM on a full-time basis. Outcome variables were sick leave, early retirement, and health-related quality of life (measured using the Short Form Health Survey, SF-36). The results showed that the risk of being granted full-time early retirement was significantly lower for females in PT and CBT compared to the CG during the 18-month follow-up period. However, the total absence from work (sick listing plus early retirement) in days over the 18-month follow-up period was not significantly different in the CG compared to the treatments. On the SF-36, women in CBT and BM reported a significantly better health-related quality of life than women in the CG at the 18-month follow-up. No significant differences for men were found on the SF-36 scales. In conclusion, the results revealed gender differences in the outcome of the treatments and that the components of this BM program yielded as good results as the whole program.