(1) Background: The Austrian supply of COVID-19 vaccine is limited for now. We aim to provide evidence-based guidance to the authorities in order to minimize COVID-19-related hospitalizations and deaths in Austria. (2) Methods: We used a dynamic agent-based population model to compare different vaccination strategies targeted to the elderly (65 ≥ years), middle aged (45–64 years), younger (15–44 years), vulnerable (risk of severe disease due to comorbidities), and healthcare workers (HCW). First, outcomes were optimized for an initially available vaccine batch for 200,000 individuals. Second, stepwise optimization was performed deriving a prioritization sequence for 2.45 million individuals, maximizing the reduction in total hospitalizations and deaths compared to no vaccination. We considered sterilizing and non-sterilizing immunity, assuming a 70% effectiveness. (3) Results: Maximum reduction of hospitalizations and deaths was achieved by starting vaccination with the elderly and vulnerable followed by middle-aged, HCW, and younger individuals. Optimizations for vaccinating 2.45 million individuals yielded the same prioritization and avoided approximately one third of deaths and hospitalizations. Starting vaccination with HCW leads to slightly smaller reductions but maximizes occupational safety. (4) Conclusion: To minimize COVID-19-related hospitalizations and deaths, our study shows that elderly and vulnerable persons should be prioritized for vaccination until further vaccines are available.