The authors evaluated the safety and clinical outcomes of uterine artery embolization (UAE) without the use of conventional iodinated contrast media for symptomatic uterine leiomyomata. Patients underwent UAE with use of CO(2) gas and a gadolinium-based contrast medium. The safety and feasibility of the technique were assessed. Patients were followed up at 24 hours, 1 month, and 6 months after UAE and yearly thereafter. UAE without iodinated contrast medium was attempted in eight patients (mean age, 42.7 years +/- 4.1), and bilateral UAE was successful in all patients. The mean fluoroscopy time was 14.9 minutes. The mean amount of gadolinium-based contrast medium used was 30.6 mL or 0.181 mmol/kg. No major complications were noted. The mean improvement in the symptom severity score was 53.8. The mean reduction in leiomyoma volume was 42%. To date, no repeat interventions have been performed. UAE with CO(2) and a gadolinium-based contrast medium is a viable treatment option for patients with a severe allergy to iodinated contrast media or renal insufficiency.