Atypical leiomyomas are histopathologically recognized by moderate to severe pleomorphic atypical tumor cells showing low mitotic counts without coagulative tumor cell necrosis. The histopathological features and clinical behavior of these tumors are unclear. The surgical management of these lesions includes myomectomy and hysterectomy. The current study presents 5 cases of women with atypical leiomyomas that were managed surgically. The clinicopathological characteristics of the patients and recurrences were analyzed. The median age of the patients was 43 years old. While 3 out of 5 patients were treated by hysterectomy (with or without salpingo-oophorectomy), the remaining 2 patients were treated by myomectomy. The median mitotic index was 3 mitotic figures/10 high-power fields. The post-operative course of all patients was uneventful, and there was no evidence of local or distant recurrence in a median follow-up time of 72 months. The treatment of choice for atypical leiomyomas is hysterectomy. However, myomectomy may be an option for fertility sparing cases. A thorough consultation with regard to the uncertain behavior of such tumors and a rigorous follow-up must be offered in such patients.