The aim of this study was to establish whether a combination of high-risk human papillomavirus (hrHPV) testing and cervical cytology could reduce colposcopy referral among women with atypical squamous cells of undetermined significance (ASCUS) or low-grade squamous intraepithelial lesion cytology. We randomized 598 women in the Helsinki area, Finland into three study groups. Different strategies of hrHPV testing, cytology and colposcopy with biopsy were used; subsequent hrHPV test results and cytological findings were compared with histology. The rates of hrHPV positivity and CIN2+ were compared. In total, 62.5% of all samples were hrHPV-positive. Altogether 45 (12.7%) CIN2 or worse (CIN2+) lesions were found in study groups A and B. Among hrHPV-positive women the rate of CIN2+ was 19.0% (n = 43), in contrast with 1.6% (n = 2) among hrHPV-negative women (relative risk = 12.2, 95% confidence interval [CI] 3.6-81.1, P < 0.001). Among all hrHPV-negative women whose cytological findings were normal or ASCUS, dysplastic lesions were uncommon (n = 4/119, 3.4%), and all were CIN1. If these women had not been referred to colposcopy, the number of colposcopies would have been reduced by 33.6%. We conclude that hrHPV testing combined with repeat cervical cytology had a high negative predictive value in patients with recurrent low-grade cervical cytology. This could reduce the referral rate to colposcopy without jeopardizing patient safety.