Background: In 2007, legislation was proposed in 24 states and the District of Columbia for school-based human papillomavirus (HPV) vaccine mandates, and mandates were enacted in Texas, Virginia, and the District of Columbia. Media coverage of these events was extensive, and media messages both reflected and contributed to controversy surrounding these legislative activities. Messages communicated through the media are an important influence on adolescent and parent understanding of school-based vaccine mandates. Methods: We conducted structured text analysis of newspaper coverage, including quantitative analysis of 169 articles published in mandate jurisdictions from 2005 to 2009, and qualitative analysis of 63 articles from 2007. Our structured analysis identified topics, key stakeholders and sources, tone, and the presence of conflict. Qualitative thematic analysis identified key messages and issues. Results: Media coverage was often incomplete, providing little context about cervical cancer or screening. Skepticism and autonomy concerns were common. Messages reflected conflict and distrust of government activities, which could negatively impact this and other youth-focused public health initiatives. Conclusions: If school health professionals are aware of the potential issues raised in media coverage of school-based health mandates, they will be more able to convey appropriate health education messages and promote informed decision-making by parents and students.