The aim of this study was to compare the relative effects of supervised aerobic exercise (AE) with a combined programme of supervised aerobic, muscle strengthening and flexibility exercises on important health outcomes in women diagnosed with fibromyalgia (FM). Sixty-four women diagnosed with FM were randomly allocated to one of three groups: AE, combined exercise (CE) or usual care control. They were assessed at baseline and after 24 weeks using the Fibromyalgia Impact Questionnaire (FIQ), Short-form Health Survey (SF-36) and Beck Depression Inventory (BDI). Functional outcomes were aerobic capacity (6-min walk test), hand-grip strength and range of motion. A 14%-15% improvement from baseline in total FIQ score was observed in the exercise groups (p≤0.02), and was accompanied by reductions in BDI scores of 8.5 (p<0.001) and 6.4 (p<0.001) points in the AE and CE group, respectively. Relative to nonexercising controls, CE evoked improvements in the SF-36 physical function (p=0.003) and bodily pain (p=0.003) domains and was more effective than AE for evoking improvements in the vitality (p=0.002) and mental health (p=0.04) domains. Greater improvements were also observed in shoulder/hip range of motion and handgrip strength in the CE group. The magnitude of improvement in FIQ scores constitutes a clinically relevant change in FM and is similar to those reported previously after AE interventions in some studies. The improvement in average BDI score in the AE group is comparable to that previously reported after AE interventions suggesting that the changes in BDI scores evoked by this exercise modality are less pronounced. Although changes in global SF-36 scores were similar across exercising groups, improvements in a broader range of SF-36 domains were observed. Furthermore, effect size changes in relation to the controls were generally greater than those observed after the programme of AE. Given the equivalent time commitment required for AE and CE, our results suggest that women with FM can gain additional health benefits by engaging in a similar volume of combined strength, flexibility and AE.