A case report of myxoid leiomyosarcoma of the uterus in a 54-year-old woman is presented as a rare variant of uterine sarcoma. Only 14 cases have been described in the literature. These tumors have a striking myxoid appearance and exhibit highly malignant behavior despite their low mitotic index. Although it is difficult to establish the nature of the neoplastic cells in the myxoid areas, both light microscopical and immunohistochemical characteristics showed features of smooth muscle cells in some of the cellular areas. Our patient had a tumor which arose in association with hyalinized benign leiomyomatous lesion. Like other reported cases of myxoid leiomyosarcoma, the tumor behaved aggressively.