The studies carried out to date on vulvodynia treatment with botulinum neurotoxin type A (BoNT/A) have followed generic injection protocols and reported contradictory outcomes on its effects. The aim of the present study was thus to propose a protocol for injecting BoNT/A into targeted painful points, to comprehensively assess the clinical effect of BoNT/A treatment and identify the risk/protective factors for successful treatment. Thirty-five vestibulodynia patients were treated with submucosal injections of incobotulinumtoxinA and assessed 8, 12 and 24 weeks after their treatment. Their clinical and pelvic statuses were assessed from self-reported questionnaires (Visual Analogue Scale (VAS), Female Sexual Function Index (FSFI), Marinoff’s Dyspareunia Scale (MDS), Hospital Anxiety and Depression Scale (HADS), Catastrophizing Scale (CS)), physical examinations and surface electromyography (sEMG). The patients reported a reduction in provoked vestibulodynia (<VAS, p < 0.01), improved sexual function (>FSFI, p < 0.01; <MDS, p = 0.01) and psychological status (<HADS, p < 0.01), and lower pelvic floor hyperactivity at rest (<sEMG amplitude, p = 0.01). Factors such as smoking, painful comorbidities, vulvar pain sensitivity and sexual function were significantly associated with successful treatment. The results indicate the beneficial effects of BoNT/A in treating vestibulodynia and reinforce the importance of adapting the treatment according to its clinical presentation and the patient’s medical background.