In 2008, the organized Czech National Cervical Cancer Screening Programme (CNCCSP) was initiated by transformation of the existing opportunistic efforts. The aim of our study was to examine recent cervical cancer burden trends and to assess the quality of the Czech National Cervical Cancer Screening Programme using a set of standard performance indicators. Our study utilized data from the national Cervical Cancer Screening Registry and the Czech National Cancer Registry. We computed internationally accepted indicators and assessed time trends and variability among screening centres. Between 1995 and 2011, the incidence of age-standardized cervical cancer decreased by 21% (1023 cases in 2011), and the mortality decreased by 35% (399 deaths in 2011). The annual coverage of the target population by cervical screening increased to 56% in 2013 (as compared with 35% in 2001). If we consider a 2-year interval (2012–2013), the estimated coverage was 77%. Over two million women underwent screening in 2013; 96% of them had a negative result. About 0.2% of smears showed cytological signs of a high-grade intraepithelial lesion or a malignancy, and the estimated positive predictive value for advanced intraepithelial neoplasia (cervical intraepithelial neoplasia grade 2+) was 79.6%. However, performance indicators show considerable heterogeneity between screening centres. The reported values of performance indicators are in line with the results of programmes that have previously been shown to be successful in terms of decreasing the cervical cancer burden, and are promising with respect to an even more pronounced decrease in cervical cancer mortality in the near future, provided that continuous quality improvement can be maintained. Linkage studies between screening, cancer and cause-of-death registers can provide further information on screening effectiveness and validity issues.