COVID-19 vaccine hesitancy among adolescents poses a challenge to the global effort to control the pandemic. This multi-country survey aimed to assess the prevalence and determinants of COVID-19 vaccine hesitancy among adolescents in sub-Saharan Africa between July and December 2021. The survey was conducted using computer-assisted telephone interviewing among adolescents in five sub-Saharan African countries, Burkina Faso, Ethiopia, Ghana, Nigeria, and Tanzania. A rural area and an urban area were included in each country (except Ghana, which only had a rural area), with approximately 300 adolescents in each area and 2662 in total. Sociodemographic characteristics and perceptions and attitudes on COVID-19 vaccines were measured. Vaccine hesitancy was defined as definitely not getting vaccinated or being undecided on whether to get vaccinated if a COVID-19 vaccine were available. Log-binomial models were used to calculate the adjusted prevalence ratios (aPRs) and 95% confidence intervals (CIs) for associations between potential determinants and COVID-19 vaccine hesitancy. The percentage of COVID-19 vaccine hesitancy was 14% in rural Kersa, 23% in rural Ibadan, 31% in rural Nouna, 32% in urban Ouagadougou, 37% in urban Addis Ababa, 48% in rural Kintampo, 65% in urban Lagos, 76% in urban Dar es Salaam, and 88% in rural Dodoma. Perceived low necessity, concerns about vaccine safety, and concerns about vaccine effectiveness were the leading reasons for hesitancy. Healthcare workers, parents or family members, and schoolteachers had the greatest impacts on vaccine willingness. Perceived lack of safety (aPR: 3.52; 95% CI: 3.00, 4.13) and lack of effectiveness (aPR: 3.46; 95% CI: 2.97, 4.03) were associated with greater vaccine hesitancy. The prevalence of COVID-19 vaccine hesitancy among adolescents is alarmingly high across the five sub-Saharan African countries, especially in Tanzania. COVID-19 vaccination campaigns among sub-Saharan African adolescents should address their concerns and misconceptions about vaccine safety and effectiveness.