Background: States in the United States have primary public health authority. This is the case with cervical cancer, and yet little is known about state policy issues affecting the comprehensive public health response. This study identifies and explores state policy issues affecting cervical cancer efforts in the United States. Methods: Key informant interviews were conducted with a purposeful sample of 15 professionals affiliated with cervical cancer prevention and treatment from national, state and local levels; across sectors: public, private and non-profit; and aspects of the work: screening, treatment and vaccine; program implementation, research, coalition work, and policy. Results: Identified policy issues were administrative and implementation oriented (“small p” policy issues). While participants recognized the importance of laws for vaccine or no cost screening access, the key policy issues preventing successful cervical cancer efforts involved 1) health system complexity; 2) general lack of state level policy, program and funding coordination; and 3) social and organizational cultural issues affecting the adoption of national recommendations and reinforcing program inertia. Conclusions: Understanding state policy issues in cervical cancer is critical for public health success. Dramatic reduction or even elimination of cervical cancer in the United States depends upon the policy work in the “little p” policy areas such as planning and health system organization to affect change. This will require greater leadership and coordination of state efforts across myriad programs. It will require health system improvements, and also the adoption of new practice and program behaviors to capitalize on available technology to reach underserved women.