We compared cytology with Hybrid Capture 2 (HC2), cobas, CLART and APTIMA Human Papillomavirus (HPV) assays in primary cervical screening at age 23-29 years based on data from the Danish Horizon study. SurePath samples were collected from 1278 women undergoing routine cytology-based screening. Abnormal cytology was managed according to the routine recommendations, and women with cytology-normal/HPV-positive samples were invited for repeated cytology and HPV testing in 1.5 years. Loss to follow-up was similar between HPV assays. ≥CIN3 was detected in 44 women. The sensitivity of HC2 for ≥CIN3 was 95% (95% confidence interval (CI): 85-99), of cobas 98% (95% CI: 88-100), of CLART 100% (95% CI: 92-100), of APTIMA 82% (95% CI: 67-92), and of cytology 59% (95% CI: 43-74). Specificity for ≥CIN3 varied between 61% (95% CI: 59-64) for cobas and 75% (95% CI: 73-78) for APTIMA, and was 94% (95% CI: 93-96) for cytology. Similar results were observed for ≥CIN2 (N = 68). HPV screening with cytological triage doubled the number of colposcopies compared to cytology screening, and increased the frequency of repeated testing by four (APTIMA) to seven (cobas) times. The positive predictive value of a referral for colposcopy was relatively high for all screening tests (≥30% for ≥CIN3, and P50% for ≥CIN2). CIN1 was detected by cytology in ∼1% of women, and in ∼2% by any of the four HPV assays. Although highly sensitive, HPV-based screening of young Danish women should be approached cautiously, as it resulted in large reductions in specificity, and increased the demand for additional testing.