Background: The study’s purpose was to evaluate the performance of a five-type HPV mRNA test to predict cervical intraepithelial neoplasia grade 3 or worse (CIN3+) during up to 12 years of follow-up. Methods: Overall, 19,153 women were recruited by gynecologists and general practitioners in different parts of Norway between 2003 and 2004. The study population comprised 9582 women of these women, aged 25–69 years with normal cytology and a valid five-type HPV mRNA test at baseline. Follow-up for CIN3+ through 2015 was conducted in the Norwegian Cervical Cancer Screening Programme. Results: The cumulative incidence of CIN3+ by baseline status for HPV mRNA-positive and mRNA-negative women were 20.8% and 1.1%, respectively (p < 0.001). Age did not affect the long-term ability of the HPV mRNA test to predict CIN3+ during follow-up. Conclusion: The low long-term risk of CIN3+ among HPV mRNA-negative women and the high long-term risk among HPV mRNA-positive women strengthen the evidence that the five-type HPV mRNA test is an appropriate screening test for women of all ages. Our findings suggest that women with a negative result may extend the screening interval up to 10 years.