The geographic and evolutionary origins of the SARS-CoV-2 Omicron variant (BA.1), which was first detected mid-November 2021 in Southern Africa, remain unknown. We tested 13,097 COVID-19 patients sampled between mid-2021 to early 2022 from 22 African countries for BA.1 by real-time RT-PCR. By November-December 2021, BA.1 had replaced the Delta variant in all African sub-regions following a South-North gradient, with a peak Rt of 4.1. Polymerase chain reaction and near-full genome sequencing data revealed genetically diverse Omicron ancestors already existed across Africa by August 2021. Mutations, altering viral tropism, replication and immune escape, gradually accumulated in the spike gene. Omicron ancestors were therefore present in several African countries months before Omicron dominated transmission. These data also indicate that travel bans are ineffective in the face of undetected and widespread infection.