Objectives: To assess the size, distribution and changes in the population of homosexual and bisexual men in Australia, and the capacity of available measures to make this estimation. Methods: We used data from five sources: the Australian Study of Health and Relationships, the Gay Community Periodic Surveys, HIV Futures, the Health in Men cohort study, the Australian National HIV and AIDS Registries and the Australian Household Census. Results: We estimated that in 2001 there were ~74 000 homosexual and bisexual men in New South Wales (NSW), ~42 000 in Victoria and ~37 000 in Queensland. There was, however, some discrepancy between datasets in the estimates of the overall proportions and distribution of homosexual and bisexual men across states. We also estimated HIV prevalence rates among homosexual and bisexual men in 2001 at ~8% in NSW, 5% in Victoria and 4% in Queensland. There were insufficient data to estimate whether the state-specific populations of homosexual men were changing with time. Conclusion: There are ~75% more homosexual and bisexual men in NSW than in Victoria and about twice as many as in Queensland. There are about two-thirds as many HIV-positive men in NSW as in Victoria and Queensland combined. Improved collection of population-based data on homosexuality are required.