Vaginal leiomyomas are normally benign smooth-muscle tumors of the vagina. These tumors are extremely rare, and their etiology is unknown. The imaging findings are those of a nonspecific well-defined enhanced soft-tissue mass centered on the vagina. Most leiomyomas are not diagnosed clinically but only on histological examination. We present a case of a vaginal leiomyoma arising from the paraurethral region with dyspareunia, dysuria, and bloody discharge. Pelvic computed tomography (CT) revealed a well-defined, heterogeneous soft-tissue mass over the retrovesical region with poor contrast enhancement. Histologic results of the incisional biopsy revealed a leiomyoma. A transvaginal approach with enucleation of the vaginal tumor was smoothly performed. The pathology confirmed the diagnosis of a vaginal leiomyoma. The immunobiochemical staining demonstrated it to be strongly positive for the estrogen receptor, progesterone receptor, epidermal growth factor receptor, and actin.