Organized introduction of prophylactic human papillomavirus (HPV) vaccination can reduce the burden of cervical cancer in developing countries. One of the most effective ways is through a national school-based program. Information on teachers is therefore important since this group may have a disproportionate influence in the success of any implementation. Objective: To assess teachers' knowledge and perception of HPV, cervical cancer and HPV vaccine prior to commencing a school-based HPV vaccination program in a multiethnic, predominantly Muslim country. Factors associated with acceptability of the vaccine were identified. Method: A bilingual questionnaire was applied to 1,500 secondary school teachers from 20 urban schools in Malaysia. Data collected were analyzed using SPSS version 17. Results: 1,166 questionnaires were returned. From this group, 46.1% had never heard of HPV while 50.9% had never had a pap smear. However, 73.8% have heard of the HPV vaccine with 75% agreeing to have it. 96% considered themselves religious with 79.8% agreeing to have the vaccine. Conclusions: A national school-based HPV immunization program can be implemented effectively in a multiethnic, cultural and religious country despite limited knowledge of HPV-related pathology among teachers. In addition, the perception that religion has a negative influence on such a program is unwarranted.