Background: Primary prevention through vaccination is a prophylactic approach aiming to reduce the risk of developing human papillomavirus (HPV)-related lesions. No mature and long-term data supported the adoption of vaccination in women undergoing conization. Methods: This is a retrospective multi-institutional study. Charts of consecutive patients undergoing conization between 2010 and 2014 were collected. All patients included had at least 5 years of follow-up. We compared outcomes of patients undergoing conization plus vaccination and conization alone. A propensity-score matching algorithm was applied in order to reduce allocation biases. The risk of developing recurrence was estimated using Kaplan-Meir and Cox hazard models. Results: Overall, charts of 1914 women were analyzed. The study group included 116 (6.1%) and 1798 (93.9%) women undergoing conization plus vaccination and conization alone, respectively. Five-year recurrence rate was 1.7% (n = 2) and 5.7% (n = 102) after conization plus vaccination and conization alone, respectively (p = 0.068). After the application of a propensity-score matching, we selected 100 patients undergoing conization plus vaccination and 200 patients undergoing conization alone. The crude number of recurrences was 2 (2%) and 11 (5.5%) for patients undergoing conization plus vaccination and conization alone, respectively (p = 0.231). Vaccination had no impact on persistent lesions (no negative examination between conization and new cervical dysplasia; p = 0.603), but reduced the risk of recurrent disease (patients who had at least one negative examination between conization and the diagnosis of recurrent cervical dysplasia; p = 0.031). Conclusions: Patients having vaccination experience a slightly lower risk of recurrence than women who had not, although not statistically significantly different. Further evidence is needed to assess the cost effectiveness of adopting vaccination in this setting.