Background: Poor attendance to cervical cancer (CC) screening is a major risk factor for CC. Efforts to capture underscreened women are considerable and once women agree to participate, the provision of longitudinal validity of the screening test is of paramount relevance. We evaluate the addition of high risk HPV test (HPV) to cervical cytology as a primary screening test among underscreened women in the longitudinal prediction of intraepithelial lesions grade 2 or worse (CIN2+). Methods: Women were included in the study if they were older than 39 years and with no evidence of cervical cytology in the previous five years within the Public Primary Health Care System in Catalonia (Spain). 1,832 underscreened women from eight public primary health areas were identified during 2007-2008 and followed-up for over three years to estimate longitudinal detection of CIN2+. Accuracy of each screening test and the combination of both to detect CIN2+ was estimated. The risk of developing CIN2+ lesions according to histology data by cytology and HPV test results at baseline was estimated using the Kaplan-Meier method. Results: At baseline, 6.7% of participants were HPV positive, 2.2% had an abnormal cytology and 1.3% had both tests positive. At the end of follow-up, 18 out of 767 (2.3%) underscreened women had a CIN2+, two of which were invasive CC. The three-year longitudinal sensitivity and specificity estimates to detect CIN2+ were 90.5% and 93.0% for HPV test and 38.2% and 97.8% for cytology. The negative predictive value was >99.0% for each test. No additional gains in validity parameters of HPV test were observed when adding cytology as co-test. The referral to colposcopy was higher for HPV but generated 53% higher detection of CIN2+ compared to cytology. Conclusions: Underscreened women had high burden of cervical disease. Primary HPV screening followed by cytology triage could be the optimal strategy to identify CIN2+ leading to longer and safe screen intervals.