To identify critical screening program factors for reducing cervical cancer mortality in Colombia.Coverage, quality, and screening follow-up were evaluated in four Colombian states with different mortality rates. A case-control study (invasive cancer and healthy controls) evaluating screening history was performed.3-year cytology coverage was 72.7%, false negative rate 49%, positive cytology follow-up 64.2%. There was no association between screening history and invasive cancer in two states having high cytology coverage but high false negative rates. Two states revealed association between deficient screening history and invasive cancer as well as lower positive-cytology follow-up.Reduced number of visits between screening and treatment is more relevant when low access to health care is present. Improved quality is a priority if access to screening is available. Suitable interventions for specific scenarios and proper appraisal of new technologies are compulsory to improve cervical cancer screening. Comprehensive process-failure audits among invasive cancer cases could improve program evaluation since mortality is a late outcome.