This paper reviews the Icelandic experience regarding the age-specific effectiveness, optimal targeted age range and intervals in cervical cancer screening and the screening implications of the HPV16/18 vaccines. The background material is based on data from a screening programme with centralized records dating back to 1964, as well as from population-based studies on the distribution of oncogenic HPV types in cancer and histologically verified CIN2-3 lesions and from the Icelandic arm of the Future II trial with Gardasil. The findings confirm significant increased rates in the screened population of CIN2-3, stage IA (microinvasive) cancer since 1979, mainly in the age group 20-34 years. These lesions start to accumulate within 3 years of a normal smear. Studies on the distribution of HPV types indicate that the marketed vaccines could lower the incidence of cancer and CIN2-3 by about 67% and 53%, respectively, after taking into account reported cross-protection. About 65% of women below 25 years of age had lesions related to the non-vaccine types and after the last normal smear these cases accumulated at the same frequency as cases with vaccine-included types. Cases with combined vaccine and non-vaccine types accumulated at a slower rate. We conclude that screening should continue to start at age 20 years, with invitations at 2-year intervals up to age 39 years and thereafter at 4-year intervals up to age 65-69 years. Current data support the conclusion that the optimal age for catch-up HPV vaccination should be considered in the context of sexual practices and the data do not support changes in the lower age limit or screening intervals for the vaccinated women.