The disease, Heartwater, caused by the Anaplasmataceae E. ruminantium, represents a major problem for tropical livestock and wild ruminants. Up to now, no effective vaccine has been available due to a limited cross protection of vaccinal strains on field strains and a high genetic diversity of Ehrlichia ruminantium within geographical locations. To address this issue, we inferred the genetic diversity and population structure of 194 E. ruminantium isolates circulating worldwide using Multilocus Sequence Typing based on lipA, lipB, secY, sodB, and sucA genes. Phylogenetic trees and networks were generated using BEAST and SplitsTree, respectively, and recombination between the different genetic groups was tested using the PHI test for recombination. Our study reveals the repeated occurrence of recombination between E. ruminantium strains, suggesting that it may occur frequently in the genome and has likely played an important role in the maintenance of genetic diversity and the evolution of E. ruminantium. Despite the unclear phylogeny and phylogeography, E. ruminantium isolates are clustered into two main groups: Group 1 (West Africa) and a Group 2 (worldwide) which is represented by West, East, and Southern Africa, Indian Ocean, and Caribbean strains. Some sequence types are common between West Africa and Caribbean and between Southern Africa and Indian Ocean strains. These common sequence types highlight two main introduction events due to the movement of cattle: from West Africa to Caribbean and from Southern Africa to the Indian Ocean islands. Due to the long branch lengths between Group 1 and Group 2, and the propensity for recombination between these groups, it seems that the West African clusters of Subgroup 2 arrived there more recently than the original divergence of the two groups, possibly with the original waves of domesticated ruminants that spread across the African continent several thousand years ago.