(1) Background: The vaccine supply is likely to be limited in 2021 due to constraints in manufacturing. To maximize the benefit from the rollout phase, an optimal strategy of vaccine allocation is necessary based on each country's epidemic status. (2) Methods: We first developed a heterogeneous population model considering the transmission matrix using maximum likelihood estimation based on the epidemiological records of individual COVID-19 cases in the Republic of Korea. Using this model, the vaccine priorities for minimizing mortality or incidence were investigated. (3) Results: The simulation results showed that the optimal vaccine allocation strategy to minimize the mortality (or incidence) was to prioritize elderly and healthcare workers (or adults) as long as the reproductive number was below 1.2 (or over 0.9). (4) Conclusion: Our simulation results support the current Korean government vaccination priority strategy, which prioritizes healthcare workers and senior groups to minimize mortality, under the condition that the reproductive number remains below 1.2. This study revealed that, in order to maintain the current vaccine priority policy, it is important to ensure that the reproductive number does not exceed the threshold by concurrently implementing nonpharmaceutical interventions.