Objective: This study aimed to determine if the Australian human papillomavirus (HPV) vaccination programme has had a population impact on presentations of genital warts. Methods: Retrospective study comparing the proportion of new clients with genital warts attending Melbourne Sexual Health Centre (MSHC) from January 2004 to December 2008. Australia provided free quadrivalent HPV vaccine to 12-18-year-old girls in a school-based programme from April 2007, and to women 26 years and younger through general practices from July 2007. Results: 36 055 new clients attended MSHC between 2004 and 2008 and genital warts were diagnosed in 3826 (10.6%; 95% CI 10.3 to 10.9). The proportion of women under 28 years with warts diagnosed decreased by 25.1% (95% CI 30.5% to 19.3%) per quarter in 2008. Comparing this to a negligible increase of 1.8% (95% CI 0.2% to 3.4%) per quarter from the start of 2004 to the end of 2007 also in women under 28 years generates strong evidence of a difference in these two trends (p<0.001). There was no evidence of a difference in trend for the quarterly proportions before and after the end of 2007 for any other subgroup, and on only one occasion was there strong evidence of a trend different to zero, for heterosexual men in 2008 in whom the average quarterly change was a decrease of 5% (95% CI 0.5% to 9.4%; p=0.031). Conclusions: The data suggest that a rapid and marked reduction in the incidence of genital warts among vaccinated women may be achievable through an HPV vaccination programme targeting women, and supports some benefit being conferred to heterosexual men.