Background The effects of COVID-19 on harmful traditional practices such Female Genital Mutilation/Cutting (FGM/C) and Child, Early or Forced Marriages (CEFM) have not been well documented. We examined how the COVID-19 pandemic has affected FGM/C and CEFM in Kenya, Uganda, Senegal, and Ethiopia. Methods A cross-sectional study design with a mixed methods approach was used. Household surveys targeting women and men aged 15–49 years in Kenya (n = 312), Uganda (n = 278), Ethiopia (n = 251), and Senegal (n = 208) were conducted. Thirty-eight in-depth interviews with programme implementers and policymakers were carried out in Kenya (n = 17), Uganda (n = 9), Ethiopia (n = 8), and Senegal (n = 4). Results In Kenya, the COVID-19 pandemic has contributed to the increase in both FGM/C and CEFM cases. Minimal increase of FGM/C cases was reported in Uganda and a significant increase in CEFM cases. In Ethiopia, the COVID-19 pandemic had a limited effect on changes in FGM/C and CEFM. In Senegal, there were minimal effects of COVID-19 on the number of FGM/C and CEFM cases. The pandemic has negatively affected implementation of interventions by the justice and legal system, the health system, and civil societies. Conclusions The pandemic has had varied effects on FGM/C and CEFM across the four countries. Across the four countries, the pandemic has negatively affected implementation of interventions by the various sectors that are responsible for preventing and responding to FGM/C and CEFM. This calls for innovative approaches in intervening in the various communities to ensure that women and girls at risk of FGM/C and CEFM or in need of services are reached during the pandemic. Evidence on how effective alternative approaches such as the use of call centres, radio talk shows and the use of local champions as part of risk communication in preventing and responding to FGM/C and CEFM amid COVID-19 is urgently required.