Uterine leiomyomas are common and can affect up to 30% of women older than 35 years. Despite this, leiomyomas of the vulva are rare, masquerading, and usually misdiagnosed as Bartholin cyst preoperatively. These smooth muscle tumors are typically painless, solitary, and well circumscribed and can affect female of any age group. We present a case of a 46-year-old female that presented to the clinic with 2-year history of right labial mass and was diagnosed as Bartholin cyst initially. The patient underwent elective excision under spinal anaesthesia and the mass was removed. The final diagnosis after microscopy result showed benign vulvar leiomyoma.