Background: In Australia, the HIV epidemic is concentrated among gay men. In recent years, the number of new diagnoses stabilised in New South Wales (NSW), but increased in other states. We reviewed the trends in sexual behaviours to explain this difference. Methods: We used the Gay Community Periodic Surveys in NSW, Victoria and Queensland during 1998–2006 and restricted analyses to the 30–49 year olds who contribute most of the HIV cases. We used the χ2-test for trends in unprotected anal intercourse with casual partners (UAIC) and regular partners, number of partners, type of relationships, knowledge of HIV serostatus and its disclosure. We compared behaviours of HIV-positive and -negative men and men across states using logistic regression adjusted for the year of report. Results: Trends in behaviours differed across the states: following a period of increase, UAIC prevalence declined in NSW since 2001, but continued to increase in Victoria and Queensland. There were other changes in NSW that were not observed in Victoria and Queensland: a decline in factors increasing HIV risk (the proportions of men with multiple sex partners and men engaging in UAIC and not knowing or not disclosing HIV serostatus) and an increase in behaviours reducing it (the proportions of men in monogamous relationships and men disclosing HIV serostatus while having UAIC). Conclusion: There were patterns of declining HIV risk behaviours in NSW, and increasing risk behaviours elsewhere, that mirrored recent changes in HIV case notifications in Australia. These data suggest that behavioural surveillance can predict changes in HIV epidemiology.