Objectives: In Australia, HIV notification rates in homosexual men, previously much higher in New South Wales, have become similar across the eastern states. We examined whether trends in HIV prevalence in community-based samples of homosexual men were consistent with the trends in HIV notifications. Methods: We examined data on self-reported HIV status from annual cross-sectional, self-completed anonymous surveys of homosexual men conducted between 1998 and 2006 in Sydney, Melbourne and Brisbane. Men were recruited at gay community venues, clinics and large gay community events. We calculated age-specific and age-standardised HIV prevalence rates. Comparisons of HIV prevalence between the three cities and across time were carried out using age-specific rates, and using logistic regression, controlling for age. Results: Men recruited from clinics had a much higher prevalence of HIV (P < 0.001) and were excluded from further analyses. Among the 50 239 completed questionnaires obtained at non-clinic sites, there was a marked decline in aged-standardised HIV prevalence in Sydney (from 14.2 to 8.98%, P < 0.001), a small decline in Brisbane (from 8.51 to 6.94%, P = 0.012) and no change in Melbourne (from 8.35 to 8.06%, P = 0.848). There were significant declines in men aged less than 50 years in Sydney, and in men aged less than 30 years in Brisbane. In Melbourne there was no significant trend in HIV at any age. Conclusion: HIV prevalence among young homosexual men has declined in Sydney, and these data suggest that HIV incidence among homosexual men is now similar in the eastern state capitals of Australia.