Buruli ulcer (BU) is an insidious neglected tropical disease. Cases are reported around the world but the rural regions of West and Central Africa are most affected. How BU is transmitted and spreads has remained a mystery, even though the causative agent, Mycobacterium ulcerans, has been known for more than 70 years. Here, using the tools of population genomics, we reconstruct the evolutionary history of M. ulcerans by comparing 165 isolates spanning 48 years and representing 11 endemic countries across Africa. The genetic diversity of African M. ulcerans was found to be restricted due to the bacterium’s slow substitution rate coupled with its relatively recent origin. We identified two specific M. ulcerans lineages within the African continent, and inferred that M. ulcerans lineage Mu_A1 existed in Africa for several hundreds of years, unlike lineage Mu_A2, which was introduced much more recently, approximately during the 19th century. Additionally, we observed that specific M. ulcerans epidemic Mu_A1 clones were introduced during the same time period in the three hydrological basins that were well covered in our panel. The estimated time span of the introduction events coincides with the Neo-imperialism period, during which time the European colonial powers divided the African continent among themselves. Using this temporal association, and in the absence of a known BU reservoir or—vector on the continent, we postulate that the so-called "Scramble for Africa" played a significant role in the spread of the disease across the continent.