Background Up to 26% of patients with early-stage cervical cancer experience relapse after primary surgery. However, little is known about which factors influence prognosis following disease recurrence. Therefore, our aims were to determine post-recurrence disease-specific survival (PR-DSS) and to identify respective prognostic factors for PR-DSS. Methods Data from 528 patients with early-stage cervical cancer who relapsed after primary surgery performed between 2007 and 2016 were obtained from the SCANN study (Surveillance in Cervical CANcer). Factors related to the primary disease and recurrence were combined in a multivariable Cox proportional hazards model to predict PR-DSS. Results The 5-year PR-DSS was 39.1% (95% confidence interval [CI] 22.7%–44.5%), median disease-free interval between primary surgery and recurrence (DFI1) was 1.5 years, and median survival after recurrence was 2.5 years. Six significant variables were identified in the multivariable analysis and were used to construct the prognostic model. Two were related to primary treatment (largest tumour size and lymphovascular space invasion) and four to recurrence (DFI1, age at recurrence, presence of symptoms, and recurrence type). The C-statistic after 10-fold cross-validation of prognostic model reached 0.701 (95% CI 0.675–0.727). Three risk-groups with significantly differing prognoses were identified, with 5-year PR-DSS rates of 81.8%, 44.6%, and 12.7%. Conclusions We developed the robust model of PR-DSS to stratify patients with relapsed cervical cancer according to risk profiles using six routinely recorded prognostic markers. The model can be utilised in clinical practice to aid decision-making on the strategy of recurrence management, and to better inform the patients.