We measured the frequency and outcome of cervical cancer prevention failures that occurred in the Papanicolaou (Pap) and colposcopy testing phases involving 1,646,580 Pap tests in 4 American hospital systems between January 1, 1998, and December 31, 2004. We defined a screening failure as a 2-step or greater discordant Pap test result and follow-up biopsy diagnosis. A total of 5,278 failures were detected (0.321% of all Pap tests); 48% and 52% of failures occurred in the Pap test and colposcopy phases, respectively. Missed squamous cancers (1 in 187,786 Pap tests), glandular cancers (1 in 19,426 Pap tests), and high-grade lesions (1 in 6,870 Pap tests) constituted 4.1% of all failures. Unnecessary repeated tests or diagnostic delays occurred in 70.8% and 63.9% of failures involving high- and low-grade lesions, respectively. We conclude that cervical cancer prevention practices are remarkably successful in preventing squamous cancers, although a high frequency of failures results in low-impact negative outcomes.