Background: Angioleiomyoma or angiomyoma or vascular leiomyoma is an unusual benign mesenchymal neoplasm. The authors present a rare case of large uterine angioleiomyoma causing severe abnormal uterine bleeding. Case: The patient, a 53-year-old, gravida 2, para 2, premenopausal Greek woman presented with a complaint of severe abnormal uterine bleeding. On gynecologic examination there was a palpable pelvic mass. Preoperative computer tomography (CT) of the abdomen and pelvis revealed an intra-abdominal mass 25 x 15 cm with abnormally increased vascularization. She underwent total abdominal hysterectomy with bilateral salpingo-oophorectomy, total omentectomy and elective pelvic lymph node dissection. Histopathology revealed uterine angioleiomyoma. Follow up 84 months after initial surgery showed no evidence of recurrence. Conclusion: Despite the type of surgery, patients with uterine angioleiomyoma have very low risk of recurrence and excellent prognosis.