Context: Gulf War veterans' illnesses (GWVI), multisymptom illnesses characterized by persistent pain, fatigue, and cognitive symptoms, have been reported by many Gulf War veterans. There are currently no effective therapies available to treat GWVI. Objective: To compare the effectiveness of cognitive behavioral therapy (CBT), exercise, and the combination of both for improving physical functioning and reducing the symptoms of GWVI. Design, Setting, and Patients: Randomized controlled 2 × 2 factorial trial conducted from April 1999 to September 2001 among 1092 Gulf War veterans who reported at least 2 of 3 symptom types (fatigue, pain, and cognitive) for more than 6 months and at the time of screening. Treatment assignment was unmasked except for a masked assessor of study outcomes at each clinical site (18 Department of Veterans Affairs [VA] and 2 Department of Defense [DOD] medical centers). Interventions: Veterans were randomly assigned to receive usual care (n=271), consisting of any and all care received from inside or outside the VA or DOD health care systems; CBT plus usual care (n=286); exercise plus usual care (n=269); or CBT plus exercise plus usual care (n=266). Exercise sessions were 60 minutes and CBT sessions were 60 to 90 minutes; both met weekly for 12 weeks. Main Outcome Measures: The primary end point was a 7-point or greater increase (improvement) on the Physical Component Summary scale of the Veterans Short Form 36-Item Health Survey at 12 months. Secondary outcomes were standardized measures of pain, fatigue, cognitive symptoms, distress, and mental health functioning. Participants were evaluated at baseline and at 3, 6, and 12 months. Results: The percentage of veterans with improvement in physical function at 1 year was 11.5% for usual care, 11.7% for exercise alone, 18.4% for CBT plus exercise, and 18.5% for CBT alone. The adjusted odds ratios (OR) for improvement in exercise, CBT, and exercise plus CBT vs usual care were 1.07 (95% confidence interval [CI], 0.63-1.82), 1.72 (95% CI, 0.91-3.23), and 1.84 (95% CI, 0.95-3.55), respectively. The OR for the overall (marginal) effect of receiving CBT (n=552) vs no CBT (n=535) was 1.71 (95% CI, 1.15-2.53) and for exercise (n=531) vs no exercise (n=556) was 1.07 (95% CI, 0.76-1.50). For secondary outcomes, exercise alone or in combination with CBT significantly improved fatigue, distress, cognitive symptoms, and mental health functioning, while CBT alone significantly improved cognitive symptoms and mental health functioning. Neither treatment had a significant impact on pain. Conclusion: Our results suggest that CBT and/or exercise can provide modest relief for some of the symptoms of chronic multisymptom illnesses such as GWVI.