Leiomyoma is a benign tumor of the mesenchymal smooth muscle that usually develops in the uterus and rarely vaginally. We detected an asymptomatic firm, non-tender, globular mobile mass approximately 4 cm in diameter at the anterior vaginal wall, mimicking genital organ prolapse leading to misdiagnosis as a cystocele, in a 45-year-old woman who presented complaining of heavy menstrual bleeding. Transvaginal ultrasonography revealed a homogeneous, hypoechoic well confined mass 37x30 mm in size, away from the urethra and the bladder. The mass was completely excised via a sagittal transvaginal approach with sharp and blunt dissection. To avoid urethral and bladder injury a catheter was introduced. Pathologic assessment of the specimen was reported as a leiomyoma. The patient was discharged doing well. At the one year follow-up no recurrence was detected. Vaginal leiomyomas occur rarely and are usually small and asymptomatic. Additionally, a leiomyosarcoma can arise vaginally, requiring prompt diagnosis and management. Therefore, during vaginal examination all vaginal sides should be inspected and palpated carefully. If any mass is encountered, it should be evaluated carefully to rule out malignancy. We report herein a case of a small vaginal leiomyoma, which had been followed with a misdiagnosis of a cystocele.