Background Australia has experienced rising notifications of HIV diagnoses despite widely available combination antiretroviral therapy (CART). New HIV diagnoses have also been younger than the average age of those living with HIV. We investigated the degree to which several risk factors could explain this rise in notifications and the younger age profile. Methods: Numbers and ages of men who have sex with men (MSM) living with HIV in Australia from 1983 to 2007 were calculated from notifications of HIV diagnoses and deaths. We compared the trend over time as well as the average ages of MSM newly diagnosed with HIV infection from 1998 to 2007 with those for: notifications of gonorrhoea and syphilis, total MSM living with HIV infection, and the component not on CART. Results: The percentage of younger MSM not taking CART has increased since 1998 (aged <30 years P < 0.001; 30–39 years P = 0.004). The trend of new HIV diagnoses was most significantly correlated with the total number of MSM living with HIV infection and the sector not taking CART (P < 0.0001). Based on similarity of average ages, MSM living with HIV infection and not taking CART was the best predictor of the increasing trend in new HIV diagnoses (99.9999% probability, Akaike information criterion). Conclusions: Our analyses suggest MSM living with HIV infection and not taking CART could be the source of the increase in HIV infections. Consequently, greater CART enrolment should decrease HIV incidence, especially in younger MSM.