Many Veterans of the 1990-1991 Gulf War report symptoms of Gulf War Illness, a condition involving numerous chronic symptoms including pain, fatigue, and mood/cognition symptoms. Little is known about this condition's etiology and treatment. This study reports outcomes from a randomized controlled single-blind trial comparing yoga to cognitive behavioral therapy for chronic pain and other symptoms of Gulf War Illness. Participants were Veterans with symptoms of GWI: chronic pain, fatigue and cognition-mood symptoms. Seventy-five Veterans were randomized to treatment via selection of envelopes from a bag (39 yoga, 36 cognitive behavioral therapy), which consisted of ten weekly group sessions. The primary outcomes of pain severity and interference (Brief Pain Inventory- Short Form) improved in the yoga condition (Cohen's d = .35, p = 0.002 and d = 0.69, p < 0.001, respectively) but not in the CBT condition (d = 0.10, p = 0.59 and d = 0.25 p = 0.23). However, the differences between groups were not statistically significant (d = 0.25, p = 0.25; d = 0.43, p = 0.076), though the difference in an a-priori-defined experimental outcome variable which combines these two variables into a total pain variable (d = 0.47, p = 0.047) was significant. Fatigue, as indicated by a measure of functional exercise capacity (6-min walk test) was reduced significantly more in the yoga group than in the CBT group (between-group d = .27, p = 0.044). Other secondary outcomes of depression, wellbeing, and self-reported autonomic nervous system symptoms did not differ between groups. No adverse events due to treatment were reported. Yoga may be an effective treatment for core Gulf War Illness symptoms of pain and fatigue, making it one of few treatments with empirical support for GWI. Results support further evaluation of yoga for treating veterans with Gulf War Illness. CLINICAL TRIAL REGISTRY: clinicaltrials.gov Registration Number NCT02378025.