To date, information on risk factors and temporal patterns of recurrences in patients with vulvar cancer is sparse. Conclusive data for an optimal surveillance strategy are lacking. This multicenter, retrospective population-based register study included 1412 patients who have been treated from 2000 to 2017 for vulvar cancer in the German districts of Upper Palatinate, Lower Bavaria, and Saxony-Anhalt. Kaplan-Meier method, and univariate and multivariate Cox regression were employed to evaluate prognostic factors and temporal course of overall survival, cumulative recurrence, and recurrence-free survival rates. After exclusion, the final study cohort comprised 829 patients. Most recurrences occurred within the first 3 years after diagnosis. Notably, a significant subset of patients were recurrent even after 5 years. The cumulative recurrence rate from all relapses was 18.6% 1 year after primary diagnosis. The recurrence rate increased to 34.7% after 3, to 41.8% after 5, and to 56.6% after 10 years post-diagnosis. The risk of relapse was significantly increased in patients over 70 years of age (hazard ratio (HR) = 2.7; p < 0.001; 95% CI 1.6-4.4), and in patients with positive nodal status N1 (HR = 2.0; p = 0.019; 95% CI 1.1-3.5) and N2/3 (HR = 2.2; p = 0.033; 95% CI 1.1-4.4). Our study provides compelling evidence that follow-up care should be carried out for longer than 5 years, especially for high-risk patients.