We report the clinicopathologic, immunohistochemical and ultrastructural features of two unusual tumors of the uterus composed of spindle and epithelioid cells strongly positive for HMB45. The two patients of 56 and 48 years of age had, respectively, hemoperitoneum and abnormal uterine bleeding. Morphologically, both tumors showed atypia and extensive necrosis. The neoplastic cells express immunohistochemically both melanogenesis (HMB45) and smooth muscle markers (actin). Ultrastructural analysis showed the presence of intracytoplasmic membrane-bound granules. We viewed these neoplasms as perivascular epithelioid cell (PEC) tumors with aggressive features. Follow-up has shown the death of one patient whereas the other is alive without disease 36 months after the surgery. The two patients were evaluated for signs of tuberous sclerosis complex, and findings were negative.