We genotyped 205 fleas from 12 sites using nine microsatellite markers. Madagascan populations of X. cheopis differed, with the mean number of alleles per locus per population ranging from 1.78 to 4.44 and with moderate to high levels of genetic differentiation between populations. Three distinct genetic clusters were identified, with different geographical distributions but with some apparent gene flow between both islands and within Malagasy regions. The approximate Bayesian computation (ABC) used to test the predominant direction of flea dispersal implied a recent population introduction from Mayotte to Madagascar, which was estimated to have occurred between 1993 and 2012. The impact of this flea introduction in terms of plague transmission in Madagascar is unclear, but the low level of flea exchange between the two islands seems to keep Mayotte free of plague for now.