Cotyledonoid dissecting leiomyoma (CDL, “Sternberg tumor”) is an unusual type of benign uterine smooth-muscle tumor with a distinctive gross appearance. Although this tumor is benign clinically and pathologically, the appearance and growth pattern are unusual; thus it may be misdiagnosed as a malignancy. A 41-year-old woman was admitted to the hospital with suspected fibroid uterus. The gynecological examination revealed a tumor corresponding to the size of approximately 18 weeks of pregnancy. The transvaginal ultrasound scan showed a 22 × 18 cm sized regular myoma-like contoured mass. She underwent laparotomy. In view of the alarming bizarre appearance, a provisional diagnosis of sarcoma was rendered, and total hysterectomy and bilateral salpingoophorectomy were performed. Simultaneously part of the small intestine adhering closely to the uterine tumor was removed with part of the mesentery. The definite pathologic examination result was cotyledonoid dissecting leiomyoma of the uterus with infiltration of tumor cells within the intestinal wall. The worrying appearance of the gross specimen is often mistaken for sarcoma or non-uterine lesions that may result in overtreatment. It is important to be aware of this entity to prevent overly aggressive treatment and preserve the fertility in young women.