Most vulvodynia patients receive combinations of several treatment modalities for their chronic painful condition. If conservative treatments fail, vestibulectomy is considered to be the ultimate treatment option for localized provoked vulvodynia (LPV). The aim of this descriptive study was to analyze relief of pain, quality of life (QoL), and complications associated with combining surgery with conservative treatments among LPV patients, both in short term and after 3 years of follow-up. The study population consisted of a retrospective patient cohort of surgically ( = 16) and only conservatively ( = 50) treated LPV patients. QoL data were assessed by a validated questionnaire (RAND-36). Data were collected by reviewing patient records and by aid of postal questionnaires. Efficacy of treatments in relief of pain was measured by numerical rating scale (NRS). Two months after surgery, the NRS scores assessed by a physician were lower in the surgery group than in patients treated only conservatively ( = 0.008). However, after a median of 36 months of follow-up, self-reported NRS scores and QoL showed no difference between the two patient cohorts. Complication rate after vestibulectomy was 18.8%. The findings suggest that combining surgery with conservative treatments may result in a more effective short-term reduction of pain. However, the effect seemed to be only temporary, as no long-term benefit was achieved.