Cytology alone, or combined with HPV16/18 genotyping, might be an acceptable method for triage in hrHPV-cervical cancer screening. Previously studied HPV-genotype based triage algorithms are based on cytology performed without knowledge of hrHPV status. The aim of this study was to explore the value of hrHPV genotyping combined with cytology as triage tool for hrHPV-positive women. 520 hrHPV-positive women were included from a randomised controlled self-sampling trial on screening non-attendees (PROHTECT-3B). Eighteen baseline triage strategies were evaluated for cytology and hrHPV genotyping (Roche Cobas 4800) on physician-sampled triage material. Sensitivity, specificity, positive predictive value (PPV), negative predictive value (NPV), referral rate, and number of referrals needed to diagnose (NRND) were calculated for CIN2+ and CIN3+. A triage strategy was considered acceptable if the NPV for CIN3+ was >98%, combined with maintenance or improvement of sensitivity and an increase in specificity in reference to the comparator, being cytology with a threshold of atypical cells of undetermined significance (ASC-US). Three triage strategies met the criteria: HPV16+ and/or >LSIL; HPV16+ and/or >HSIL; (HPV16+ and/or HPV18+) and/or >HSIL. Combining HPV16+ and/or >HSIL yielded the highest specificity (74.9%, 95% CI 70.5-78.9), with a sensitivity (94.4%, 95% CI 89.0-97.7) similar to the comparator (93.5%, 95% CI 87.7-97.1), and a decrease in referral rate from 52.2% to 39.5%. In case of prior knowledge of hrHPV presence, triage by cytology testing can be improved by adjusting its threshold, and combining it with HPV16/18 genotyping. These strategies improve the referral rate and specificity for detecting CIN3+ lesions, while maintaining adequate sensitivity.