Background: Quadrivalent human papillomavirus (HPV) vaccine has high efficacy in clinical trials but no reports describe its effects at a population level. From July, 2007, Australia was the first country to fund a vaccination programme for all women aged 12-26 years. We established a national surveillance network in Australia and aimed to identify trends in diagnoses of genital warts in 2004-09. Methods: We obtained standardised data for demographic factors, frequency of genital warts, HPV vaccination status, and sexual behaviour for new patients attending eight sexual health services in Australia between January, 2004, and December, 2009. We used χ2 analysis to identify significant trends in proportions of patients diagnosed with warts in periods before and after vaccination began. Our primary group of interest was female Australian residents who were eligible for free vaccination, although data were assessed for patients ineligible for free vaccination, including women older than 26 years of age, non-resident women, and men. Findings: Among 112 083 new patients attending sexual health services, we identified 9867 (9%) cases of genital warts. Before the vaccine programme started, there was no change in proportion of women or heterosexual men diagnosed with genital warts. After vaccination began, a decline in number of diagnoses of genital warts was noted for young female residents (59%, ptrend<0·0001). No significant decline was noted in female non-residents, women older than 26 years in July, 2007, or in men who have sex with men. However, proportionally fewer heterosexual men were diagnosed with genital warts during the vaccine period (28%, ptrend<0·0001), and this effect was more pronounced in young men. By 2009, 65·1% of female Australian residents who were eligible for free vaccine reported receipt of quadrivalent or unknown HPV vaccine. Interpretation: The decrease in frequency of genital warts in young Australian women resulting from the high coverage of HPV vaccination might provide protective effects in heterosexual men through herd immunity. Funding: CSL Biotherapies.