To determine and compare short- and long-term effects of aerobic exercise (AE), stress management treatment (SMT), and treatment-as-usual (TAU) in fibromyalgia, 60 patients were randomized to 14 weeks of treatment by either AE, SMT or TAU. Outcome measures at baseline, midway through treatment, at treatment completion, and at 4 year follow up included a patient made drawing of pain distribution, dolorimetry of tender points, ergometer cycle test, global subjective improvement, and VAS registrations of: pain, disturbed sleep, lack of energy, and depression. Both AE and SMT showed positive short-term effects. AE was the overall most effective treatment, despite being subject to the most sceptical patient attitude prior to the study. At follow up, there were no obvious group differences in symptom severity, which for AE seemed to be due to a considerable compliance problem.