The coronavirus disease 2019 (COVID-19) pandemic is a global threat, challenging health services’ provision and utilization. This study aimed to assess compulsory vaccination coverage in 12 Sub-Saharan African countries two years following the COVID-19 pandemic using the Health Belief Model. A cross-sectional survey was conducted from November 1 to December 15, 2022. Multivariate logistic regression was conducted to identify the determinants of vaccination coverage. Among the 5032 respondents, 73.1% reported that their children received compulsory vaccination. The lowest coverage was observed in Ghana (36.5%), while the highest was in Burkina Faso and Congo (92.0%). Factors associated with non-vaccination included older mothers (adjusted odds ratio (AOR) = 1.04, 95%CI: 1.03–1.05), lower mothers’ education, older children (AOR = 0.76, 95%CI: 0.60–0.96), children with chronic illnesses (AOR = 0.55, 95%CI: 0.45–0.66), and difficult accessibility to healthcare facilities (AOR = 11.27, 95%CI: 9.48–13.44). Low perceived risk, in which non-vaccinated children were believed to be at no higher risk for infectious diseases and the disease severity would not worsen among non-vaccinated children, increased the likelihood of non-vaccination (AOR = 2.29, 95%CI: 1.75–2.99 and AOR = 2.12, 95%CI: 1.64–2.73, respectively). Perceiving vaccines as unnecessary, and needless for breastfed babies increased the probability of non-vaccination (AOR = 1.38, 95%CI: 1.10–1.73 and AOR = 1.69, 95%CI: 1.31–2.19, respectively). Higher odds of non-vaccination were found when the provision of vaccine information did not motivate parents to vaccinate their children (AOR = 4.29, 95%CI: 3.15–5.85). Conversely, believing that vaccines were safe for children decreased the odds of non-vaccination (AOR = 0.72, 95%CI: 0.58–0.88). Parental perceptions and concerns should be considered in interventions aiming to increase compulsory vaccine acceptance and coverage.
