An 11-year-old Labrador Retriever bitch with a history of intermittent, sanguineous vaginal discharge of a six-month duration was presented. During exploratory laparotomy, two well-delineated, intramural masses were identified bilaterally in the uterine horns. Histopathologic examination of the mass on the left horn showed that it was a typical leiomyoma. However, the second mass appeared with an unusual coexistence of histological lesions, involving epithelial tissue foci, mild focal adenomyosis, and cystic endometrial hyperplasia. Interestingly, such combination was never encountered before in dogs. Although uterine leiomyoma is quite usual in the reproductive system of female dogs, this case resembled relevant cases of human uterine adenomyomas in morphology, and thus it was offered a similar tentative diagnosis.