Eastern Europe continues to have the highest rates of cancer of the uterine cervix (CUC) and human papillomavirus (HPV) infection in Europe. Aim: The aim of this study was to investigate CUC trends in Bulgaria in the context of a lack of a population-based screening program and a demographic crisis. Methodology: This was a retrospective study of 7861 CUC patients who were registered in the Bulgarian National Cancer Registry (BNCR) between 2013 and 2020 and followed up with until March 2022. We used descriptive statistics and modeling to assess temporal trends in new CUC incidence rates and identify factors associated with survival. Results: Bulgaria’s population has decreased by 11.5% between 2011 and 2021. The CUC incidence rate decreased from 29.5/100,000 in 2013 to 23.2/100,000 in 2020 but remains very high. The proportion of patients diagnosed in earlier stages of CUC has decreased over time. Up to 19% of patients with CUC in Bulgaria are diagnosed between the age of 35 and 44 years. The median survival was 101.5 months, with some improvement in later years (adjusted HR = 0.83 for 2017–2020). Conclusions: In countries with well-established population-based screening, CUC is nowadays considered a rare disease. However, it is not considered rare in Bulgaria. Population-based screening starting at an earlier age is the fastest way to improve outcomes.