Background Uterine fibroids are the most common tumour in women of reproductive age and are associated with heavy menstrual bleeding, abdominal discomfort, subfertility and reduced quality of life. For women wishing to retain their uterus and who do not respond to medical treatment, myomectomy and uterine artery embolisation are therapeutic options. Objectives We examined the clinical effectiveness and cost-effectiveness of uterine artery embolisation compared with myomectomy in the treatment of symptomatic fibroids. Design A multicentre, open, randomised trial with a parallel economic evaluation. Setting Twenty-nine UK hospitals. Participants Premenopausal women who had symptomatic uterine fibroids amenable to myomectomy or uterine artery embolisation were recruited. Women were excluded if they had significant adenomyosis, any malignancy or pelvic inflammatory disease or if they had already had a previous open myomectomy or uterine artery embolisation. Interventions Participants were randomised to myomectomy or embolisation in a 1 : 1 ratio using a minimisation algorithm. Myomectomy could be open abdominal, laparoscopic or hysteroscopic. Embolisation of the uterine arteries was performed under fluoroscopic guidance. Main outcome measures The primary outcome was the Uterine Fibroid Symptom Quality of Life questionnaire (with scores ranging from 0 to 100 and a higher score indicating better quality of life) at 2 years, adjusted for baseline score. The economic evaluation estimated quality-adjusted life-years (derived from EuroQol-5 Dimensions, three-level version, and costs from the NHS perspective). Results A total of 254 women were randomised – 127 to myomectomy (105 underwent myomectomy) and 127 to uterine artery embolisation (98 underwent embolisation). Information on the primary outcome at 2 years was available for 81% (n = 206) of women. Primary outcome scores at 2 years were 84.6 (standard deviation 21.5) in the myomectomy group and 80.0 (standard deviation 22.0) in the uterine artery embolisation group (intention-to-treat complete-case analysis mean adjusted difference 8.0, 95% confidence interval 1.8 to 14.1, p = 0.01; mean adjusted difference using multiple imputation for missing responses 6.5, 95% confidence interval 1.1 to 11.9). The mean difference in the primary outcome at the 4-year follow-up time point was 5.0 (95% CI –1.4 to 11.5; p = 0.13) in favour of myomectomy. Perioperative and postoperative complications from all initial procedures occurred in similar percentages of women in both groups (29% in the myomectomy group vs. 24% in the UAE group). Twelve women in the uterine embolisation group and six women in the myomectomy group reported pregnancies over 4 years, resulting in seven and five live births, respectively (hazard ratio 0.48, 95% confidence interval 0.18 to 1.28). Over a 2-year time horizon, uterine artery embolisation was associated with higher costs than myomectomy (mean cost £7958, 95% confidence interval £6304 to £9612, vs. mean cost £7314, 95% confidence interval £5854 to £8773), but with fewer quality-adjusted life-years gained (0.74, 95% confidence interval 0.70 to 0.78, vs. 0.83, 95% confidence interval 0.79 to 0.87). The differences in costs (difference £645, 95% confidence interval –£1381 to £2580) and quality-adjusted life-years (difference –0.09, 95% confidence interval –0.11 to –0.04) were small. Similar results were observed over the 4-year time horizon. At a threshold of willingness to pay for a gain of 1 QALY of £20,000, the probability of myomectomy being cost-effective is 98% at 2 years and 96% at 4 years. Limitations There were a substantial number of women who were not recruited because of their preference for a particular treatment option. Conclusions Among women with symptomatic uterine fibroids, myomectomy resulted in greater improvement in quality of life than did uterine artery embolisation. The differences in costs and quality-adjusted life-years are very small. Future research should involve women who are desiring pregnancy. Trial registration This trial is registered as ISRCTN70772394. Funding This study was funded by the National Institute for Health and Care Research (NIHR) Health Technology Assessment programme, and will be published in full in Health Technology Assessment; Vol. 26, No. 22. See the NIHR Journals Library website for further project information.