Objective: To determine the impact of comprehensiveness of cytology registration on the proportion of cervical cancer patients without a recent screening history. Methods: For Danish women diagnosed with cervical cancer in 2003-2007, we used cytology data from the nationwide Danish Pathology Data Bank and the National Health Service Register. In five steps, we included data from an increasing number of cervical screening laboratories into the analysis, and calculated the proportions of screened women who had cytology registered in two screening rounds prior to the cancer diagnosis. Results: In total, 1867 cervical cancer patients were included in the analysis. When looking only at the screening history in the laboratory that diagnosed the cancer, it appeared that only 40% of women were screened in the last two rounds. This proportion increased to 55% when nationwide screening data were used. This corresponded to a 25% decrease in the proportion of patients without a recent screening history. Conclusion: The level of comprehensiveness of screening data makes a measurable difference when evaluating the screening histories of women with cervical cancer. It is important that actions for the improvement of a screening program are based on comprehensive cytology registrations.