Background The role of environmental factors in driving adaptive trajectories of living organisms is still being debated. This is even more important to understand when dealing with important neglected diseases and their vectors. Methodology/Principal Findings In this paper, we analysed genetic divergence, computed from seven microsatellite loci, of 614 tsetse flies (Glossina palpalis gambiensis and Glossina palpalis palpalis, major vectors of animal and human trypanosomes) from 28 sites of West and Central Africa. We found that the two subspecies are so divergent that they deserve the species status. Controlling for geographic and time distances that separate these samples, which have a significant effect, we found that G. p. gambiensis from different landscapes (Niayes of Senegal, savannah and coastal environments) were significantly genetically different and thus represent different ecotypes or subspecies. We also confirm that G. p. palpalis from Ivory Coast, Cameroon and DRC are strongly divergent. Conclusions/Significance These results provide an opportunity to examine whether new tsetse fly ecotypes might display different behaviour, dispersal patterns, host preferences and vectorial capacities. This work also urges a revision of taxonomic status of Glossina palpalis subspecies and highlights again how fast ecological divergence can be, especially in host-parasite-vector systems.