Every year in the United States more than 12,000 women are diagnosed with cervical cancer, a disease principally caused by human papillomavirus (HPV). Bivalent and quadrivalent HPV vaccines protect against 66% of HPV-associated cervical cancers, and a new nonavalent vaccine protects against an additional 15% of cervical cancers. However, vaccination policy varies across states, and migration between states interdependently dilutes state-specific vaccination policies. To quantify the economic and epidemiological impacts of switching to the nonavalent vaccine both for individual states and for the nation as a whole, we developed a model of HPV transmission and cervical cancer incidence that incorporates state-specific demographic dynamics, sexual behavior, and migratory patterns. At the national level, the nonavalent vaccine was shown to be cost-effective compared with the bivalent and quadrivalent vaccines at any coverage despite the greater per-dose cost of the new vaccine. Furthermore, the nonavalent vaccine remains cost-effective with up to an additional 40% coverage of the adolescent population, representing 80% of girls and 62% of boys. We find that expansion of coverage would have the greatest health impact in states with the lowest coverage because of the decreasing marginal returns of herd immunity. Our results show that if policies promoting nonavalent vaccine implementation and expansion of coverage are coordinated across multiple states, all states benefit both in health and in economic terms.