A vaccine, when available, will likely become our best tool to control the current COVID-19 pandemic. Even in the most optimistic scenarios, vaccine shortages will likely occur. Using an age-stratified mathematical model, we determined optimal vaccine allocation for four different metrics (deaths, symptomatic infections, and maximum non-ICU and ICU hospitalizations) under a wide variety of assumptions. We find that a vaccine with effectiveness ≥50% would be enough to substantially mitigate the ongoing pandemic provided that a high percentage of the population is optimally vaccinated. When minimizing deaths, we find that for low vaccine effectiveness, it is optimal to allocate vaccine to high-risk (older) age-groups first. In contrast, for higher vaccine effectiveness, there is a switch to allocate vaccine to high-transmission (younger) age-groups first for high vaccination coverage. While there are other societal and ethical considerations, this work can provide an evidence-based rationale for vaccine prioritization.