The success of screening, an important cancer prevention tool, depends on the quality and efficiency of protocols and guidelines for screening and follow-up. However, even centrally organized screening programs such as the Dutch cervical screening program occasionally show problems in performance. To improve this program, the screening scheme, follow-up, administration and financing protocols and guidelines were thoroughly changed in 1996. This study evaluates the consequences for the performance of the national program. Five-year coverage rate, the proportion of screened women sent to follow-up, follow-up compliance and duration, and the yearly number of Pap smears before and after the changes in 1996 were compared. Five-year coverage increased substantially in the added target age groups (30-34, and 54-60 years); in the old target age group (35-53 years) it remained around 80%. The percentage of screened women sent to follow-up decreased from almost 19-3% per screening round, due to a more restrictive use of the Pap 2 classification, and an evidence-based cessation of follow-up of negative smears without endocervical cells. Follow-up compliance has improved, and the average time until a woman is either referred or rejoins the regular screening schedule, has become shorter. The total number of smears, a strong determinant of screening costs, has decreased by 20% primarily due to the changed follow-up recommendations. In conclusion, the 1996 changes in protocols and guidelines, and their implementation have increased coverage and efficiency, and decreased the screening-induced negative side effects.