BACKGROUND: A few studies have assessed the epidemiological impact and the cost-effectiveness of COVID-19 vaccines in settings where most of the population had been exposed to SARS-CoV-2 infection. METHODS: We conducted a cost-effectiveness analysis of COVID-19 vaccine in Kenya from a societal perspective over a 1.5-year time frame. An age-structured transmission model assumed at least 80% of the population to have prior natural immunity when an immune escape variant was introduced. We examine the effect of slow (18 months) or rapid (6 months) vaccine roll-out with vaccine coverage of 30%, 50% or 70% of the adult (>18 years) population prioritising roll-out in those over 50-years (80% uptake in all scenarios). Cost data were obtained from primary analyses. We assumed vaccine procurement at US$7 per dose and vaccine delivery costs of US$3.90-US$6.11 per dose. The cost-effectiveness threshold was US$919.11. FINDINGS: Slow roll-out at 30% coverage largely targets those over 50 years and resulted in 54% fewer deaths (8132 (7914-8373)) than no vaccination and was cost saving (incremental cost-effectiveness ratio, ICER=US$-1343 (US$-1345 to US$-1341) per disability-adjusted life-year, DALY averted). Increasing coverage to 50% and 70%, further reduced deaths by 12% (810 (757-872) and 5% (282 (251-317) but was not cost-effective, using Kenya's cost-effectiveness threshold (US$919.11). Rapid roll-out with 30% coverage averted 63% more deaths and was more cost-saving (ICER=US$-1607 (US$-1609 to US$-1604) per DALY averted) compared with slow roll-out at the same coverage level, but 50% and 70% coverage scenarios were not cost-effective. INTERPRETATION: With prior exposure partially protecting much of the Kenyan population, vaccination of young adults may no longer be cost-effective.