Low- and middle-income countries are implementing COVID-19 vaccination strategies in light of varying vaccine efficacies and costs, supply shortages, and resource constraints. Here, we use a microsimulation model to evaluate clinical outcomes and cost-effectiveness of a COVID-19 vaccination program in South Africa. We varied vaccination coverage, pace, acceptance, effectiveness, and cost as well as epidemic dynamics. Providing vaccines to at least 40% of the population and prioritizing vaccine rollout prevented >9 million infections and >73,000 deaths and reduced costs due to fewer hospitalizations. Model results were most sensitive to assumptions about epidemic growth and prevalence of prior immunity to SARS-CoV-2, though the vaccination program still provided high value and decreased both deaths and health care costs across a wide range of assumptions. Vaccination program implementation factors, including prompt procurement, distribution, and rollout, are likely more influential than characteristics of the vaccine itself in maximizing public health benefits and economic efficiency.