Background: A vaccine program is underway to protect women against human papillomavirus (HPV) and thus cervical cancer. Previous studies have reported very low levels of HPV knowledge and there has been concern that preventative vaccines might not be readily accepted, given that HPV is transmitted sexually and the optimal time for vaccination is before sexual debut. Methods: A computer-assisted telephone survey was carried out with a representative sample of 1100 women aged 18 to 61 years, randomly selected from households in Victoria, Australia, to investigate knowledge and attitudes about HPV and attitudes towards HPV vaccination. Results: Half of the participants (51%) had heard of HPV; most reported learning about it from the media. Most women indicated they would trust their general practitioner (96.3%), a gynaecologist or specialist doctor (99.6%), or a women’s health service (97.0%) for information about HPV. Few women (11.9%) had ever sought information about HPV and only 14.8% of the total sample had ever discussed HPV with a friend. Strong support was found for vaccination in general and there was also significant support for a HPV vaccine. Conclusion: The present study documents ways in which women learn about HPV and indicates the potential for success of a vaccination program.