Background: Recently published results from a large randomized trial (Canadian Cervical Cancer Screening Trial study group) suggest that human papillomavirus testing followed by Pap smear-based triage for human papillomavirus positive women may be an effective way to screen women for cervical cancer. We determined the potential cost-effectiveness of including human papillomavirus tests for cervical cancer screening for Canada and three provinces: Alberta, Newfoundland and Ontario. Methods: We developed four Markov decision models using data from relevant Canadian and provincial studies and databases. The models were used to determine the number of false positive test results, cancers, lifetime costs and life-expectancy for 27 different screening strategies that varied by age to begin screening (18 or 25 years), screening interval (one, two, three, or five years) and whether the currently recommended strategy (screening every year from age 18 until 21 and then every three years afterwards with conventional Paps) was conducted prior to age 25. Strategies were compared using incremental cost-effectiveness ratios. Results: Screening strategies beginning at age 18 were associated with a substantial increase in the number of false-positive test results but only small differences in the number of cancers compared to the same strategy conducted beginning at age 25. Strategies of human papillomavirus testing first, followed by triage with Pap smears were associated with lower costs and greater increases in life-expectancy than the currently recommended screening strategy in Canada. Conclusion: A strategy of human papillomavirus testing beginning at age 25, with Pap triage for women with positive human papillomavirus results may be more effective at reducing cervical cancer at a lower cost than the current recommended strategy for screening in Canada.