We estimated the size of the population of gay-identified men who have sex with men (gay men) eligible for PrEP in Australia under the current national PrEP guidelines. Using input indicators from the Australian Bureau of Statistics, the national representative survey Second Australian Study of Health and Relationships, and national HIV- behavioural surveillance, we calculated the size of the population of sexually active gay men and estimated a range for the number eligible for PrEP using different scenarios based on the guidelines. In 2015, an estimated 108,850 sexually-active 16-69-year-old gay men were classified as at risk of acquiring HIV in Australia. Of these men, 10,558 to 30,913 (9.7%-28.4%) were classified as being at high risk and therefore eligible for PrEP, most commonly due to recent receptive condomless intercourse with casual partners (6.1% to 15.5%), STI infections (5.4% to 10.6%) or the use of crystal methamphetamine (1.4% to 9.4%). The higher estimates included men who may have been at HIV risk for shorter time periods or with fewer partners. Australian PrEP guidelines recommend targeting PrEP to people at high HIV risk. Our estimation of potential PrEP users informed PrEP implementation in Australia. The choice of PrEP eligibility criteria, and interpretation of the guidelines, strongly affects the population estimates. In the future, higher numbers of gay men may become eligible for PrEP, because the estimates are largely defined by and follow trends in condomless anal intercourse. Our estimation methods can be adapted to other settings.