The African continent has some of the worlds lowest COVID-19 vaccination rates. While the limited availability of vaccines is a contributing factor, COVID-19 vaccine hesitancy among health care providers (HCP) is another factor that could adversely affect efforts to control infections on the continent. We sought to understand the extent of COVID-19 vaccine hesitancy among HCP, and its contributing factors in Africa. We evaluated COVID-19 vaccine hesitancy among 1,499 HCP enrolled in a repeated cross-sectional telephone survey in Burkina Faso, Ethiopia, Nigeria, Tanzania and Ghana. We defined COVID-19 vaccine hesitancy among HCP as self-reported responses of definitely not, maybe, unsure, or undecided on whether to get the COVID-19 vaccine, compared to definitely getting the vaccine. We used Poisson regression models to evaluate factors influencing vaccine hesitancy among HCP. Approximately 65.6% were nurses and the mean age ({+/-}SD) of participants was 35.8 ({+/-}9.7) years. At least 67% of the HCP reported being vaccinated. Reasons for low COVID-19 vaccine uptake included concern about vaccine effectiveness, side effects and fear of receiving unsafe and experimental vaccines. COVID-19 vaccine hesitancy affected 45.7% of the HCP in Burkina Faso, 25.7% in Tanzania, 9.8% in Ethiopia, 9% in Ghana and 8.1% in Nigeria. Respondents reporting that COVID-19 vaccines are very effective (RR0.21, 95% CI0.08, 0.55), and older HCP (45 or older vs.20-29 years, RR0.65, 95% CI 0.44,0.95) were less likely to be vaccine-hesitant. Nurses were more likely to be vaccine-hesitant (RR 1.38, 95% CI 1.00,1.89) compared to doctors. We found higher vaccine hesitancy among HCP in Burkina Faso and Tanzania. Information asymmetry among HCP, beliefs about vaccine effectiveness and the endorsement of vaccines by the public health institutions may be important. Efforts to address hesitancy should address information and knowledge gaps among different cadres of HCP and should be coupled with efforts to increase vaccine supply.