The performance of different clinical screening algorithms comprising point-of-care HPV-DNA testing using self-collected vaginal ('V') specimens, and visual inspection of the cervix with acetic acid (VIA) was evaluated in Papua New Guinea. Women aged 30-59 years provided V specimens that were tested at point-of-care using the Xpert HPV Test (Cepheid, Sunnyvale, CA). A clinician-collected cervical ('C') specimen was then collected for point-of-care Xpert testing, and liquid-based cytology (LBC). Following this, VIA examination was conducted, blind to HPV test results, and ablative cervical cryotherapy provided if indicated. Detection of high-grade squamous intraepithelial lesion (HSIL) by LBC was the reference standard used to evaluate clinical screening algorithms. Of 1005 women, 36 had HSIL+. Xpert HPV Test performance using V specimens (sensitivity 91.7%, specificity 87.0%, PPV 34.0%, NPV 99.3%) was superior to VIA examination alone (51.5%, 81.4%, 17.5%, 95.6% respectively) in predicting underlying HSIL+. A screening algorithm comprising V specimen HPV testing followed by VIA examination had low sensitivity (45.5%) but comparable specificity, PPV and NPV to HPV testing alone (96.3%, 45.5%, 96.3% respectively). A 'test-and-treat' screening algorithm based on point-of-care HPV testing of V specimens had superior performance compared with either VIA examination alone, or a combined screening algorithm comprising HPV testing plus VIA.