Using mathematical models of cervical cancer for the northern and southern regions of Vietnam, we assessed the cost-effectiveness of cervical cancer prevention strategies and the tradeoffs between a national and region-based policy in Vietnam. With 70% vaccination and screening coverage, lifetime risk of cancer was reduced by 20.4-76.1% with vaccination of pre-adolescent girls and/or screening of older women. Only when the cost per vaccinated girl was low (i.e., <I$25) was vaccination combined with screening (three times per lifetime or every 5 years) favored in both regions; at high costs per vaccinated girl (i.e., >I$100), screening alone was most cost-effective. When optimal policies differed between regions, implementing a national strategy resulted in health and economic inefficiencies. HPV vaccination appears to be an attractive cervical cancer prevention strategy for Vietnam, provided high coverage can be achieved in young pre-adolescent girls, cost per vaccinated girl is <I$25 (i.e., <$5 per dose), and screening is offered at older ages.