The purpose of this study was to compare the effects of aerobic training with a muscle-strengthening program in patients with fibromyalgia. Thirty women with fibromyalgia were randomized to either an aerobic exercise (AE) program or a strengthening exercise (SE) program for 8 weeks. Outcome measures included the intensity of fibromyalgia-related symptoms, tender point count, fitness (6-min walk distance), hospital anxiety and depression (HAD) scale, and short-form health survey (SF-36). There were significant improvements in both groups regarding pain, sleep, fatigue, tender point count, and fitness after treatment. HAD-depression scores improved significantly in both groups while no significant change occurred in HAD-anxiety scores. Bodily pain subscale of SF-36 and physical component summary improved significantly in the AE group, whereas seven subscales of SF-36, physical component summary, and mental component summary improved significantly in the SE group. When the groups were compared after treatment, there were no significant differences in pain, sleep, fatigue, tender point count, fitness, HAD scores, and SF-36 scores. AE and SE are similarly effective at improving symptoms, tender point count, fitness, depression, and quality of life in fibromyalgia.