Background: Tests for the DNA of high-risk types of human papillomavirus (HPV) have a higher sensitivity for cervical intraepithelial neoplasia grade 3 or worse (CIN3+) than does cytological testing, but the necessity of such testing in cervical screening has been debated. Our aim was to determine whether the effectiveness of cervical screening improves when HPV DNA testing is implemented. Methods: Women aged 29-56 years who were participating in the regular cervical screening programme in the Netherlands were randomly assigned to combined cytological and HPV DNA testing or to conventional cytological testing only. After 5 years, combined cytological and HPV DNA testing were done in both groups. The primary outcome measure was the number of CIN3+ lesions detected. Analyses were done by intention to treat. This trial is registered as an International Standard Randomised Controlled Trial, number ISRCTN20781131. Findings: 8575 women in the intervention group and 8580 in the control group were recruited, followed up for sufficient time (≥6·5 years), and met eligibility criteria for our analyses. More CIN3+ lesions were detected at baseline in the intervention group than in the control group (68/8575 vs 40/8580, 70% increase, 95% CI 15-151; p=0·007). The number of CIN3+ lesions detected in the subsequent round was lower in the intervention group than in the control group (24/8413 vs 54/8456, 55% decrease, 95% CI 28-72; p=0·001). The number of CIN3+ lesions over the two rounds did not differ between groups. Interpretation: The implementation of HPV DNA testing in cervical screening leads to earlier detection of CIN3+ lesions. Earlier detection of such lesions could permit an extension of the screening interval.