The worldwide endeavour to develop safe and effective COVID-19 vaccines has been extraordinary, and vaccination is now underway in many countries. However, the doses available in 2021 are likely to be limited. We extended a mathematical model of SARS-CoV-2 transmission across different country settings to evaluate the public health impact of potential vaccines using WHO-developed target product profiles. We identified optimal vaccine allocation strategies within- and between-countries to maximise averted deaths under constraints on dose supply. We found that the health impact of SARS-CoV-2 vaccination depends on the cumulative population-level infection incidence when vaccination begins, the duration of natural immunity, the trajectory of the epidemic prior to vaccination, and the level of healthcare available to effectively treat those with disease. Within a country we find that for a limited supply (doses for <20% of the population) the optimal strategy is to target the elderly. However, with a larger supply, if vaccination can occur while other interventions are maintained, the optimal strategy switches to targeting key transmitters to indirectly protect the vulnerable. As supply increases, vaccines that reduce or block infection have a greater impact than those that prevent disease alone due to the indirect protection provided to high-risk groups. Given a 2 billion global dose supply in 2021, we find that a strategy in which doses are allocated to countries proportional to population size is close to optimal in averting deaths and aligns with the ethical principles agreed in pandemic preparedness planning.