BACKGROUND: Pre-exposure prophylaxis (PrEP), a WHO-recommended HIV prevention method for people at high risk for acquiring HIV, is being increasingly implemented in many countries. Setting programmatic targets, particularly in generalised epidemics, could incorporate estimates of the size of the population likely to be eligible for PrEP using incidence-based thresholds. We estimated the proportion of men and women who would be eligible for PrEP and the number of HIV infections that could be averted in Malawi, Mozambique, and Zambia using prioritisation based on age, sex, geography, and markers of risk. METHODS AND FINDINGS: We analysed the latest nationally representative Demographic and Health Surveys (DHS) of Malawi, Mozambique, and Zambia to determine the proportion of adults who report behavioural markers of risk for HIV infection. We used prevalence ratios (PRs) to quantify the association of these factors with HIV status. Using a multiplier method, we combined these proportions with the number of new HIV infections by district, derived from district-level modelled HIV estimates. Based on these numbers, different scenarios were analysed for the minimum number of person-years on PrEP needed to prevent 1 HIV infection (NNP). An estimated total of 38,000, 108,000, and 46,000 new infections occurred in Malawi, Mozambique, and Zambia in 2016, corresponding with incidence rates of 0.43, 0.63, and 0.57 per 100 person-years. In these countries, 9%-20% of new infections occurred among people with a sexually transmitted infection (STI) in the past 12 months and 40%-42% among people with either an STI or a non-regular sexual partner (NP) in the past 12 months (STINP). The models estimate that around 50% of new infections occurred in districts with incidence rates ≥1.0% in Mozambique and Zambia and ≥0.5% in Malawi. In Malawi, Mozambique, and Zambia, 35.1%, 21.9%, and 12.5% of the population live in these high-incidence districts. In the most parsimonious scenario, if women aged 15-34 years and men 20-34 years with an STI in the past 12 months living in high-incidence districts were to take PrEP, it would take a minimum of 65.8 person-years on PrEP to avert 1 HIV infection per year in Malawi, 35.2 in Mozambique, and 16.4 in Zambia. Our findings suggest that 3,300, 5,200, and 1,700 new infections could be averted per year in the 3 countries, respectively. Limitations of our study are that these values are based on modelled estimates of HIV incidence and self-reported behavioural risk factors from national surveys. CONCLUSIONS: A large proportion of new HIV infections in these 3 African countries were estimated to occur among people who had either an STI or an NP in the past year, providing a straightforward means to set PrEP targets. Greater prioritisation of PrEP by district, sex, age, and behavioural risk factors resulted in lower NNPs thereby increasing PrEP cost-effectiveness, but also diminished the overall impact on reducing new infections.