Background: African animal trypanosomosis is a major obstacle to the development of more efficient and sustainable livestock production systems in West Africa. Riverine tsetse species such as Glossina palpalis gambiensis Vanderplank and Glossina tachinoides Westwood are the major vectors. A wide variety of control tactics is available to manage these vectors, but their removal will in most cases only be sustainable if the control effort is targeting an entire tsetse population within a circumscribed area. Methodology/Principal Findings: In the present study, genetic variation at microsatellite DNA loci was used to examine the population structure of G. p. gambiensis and G. tachinoides inhabiting four adjacent river basins in Burkina Faso, i.e. the Mouhoun, the Comoe, the Niger and the Sissili River Basins. Isolation by distance was significant for both species across river basins, and dispersal of G. tachinoides was similar to 3 times higher than that of G. p. gambiensis. Thus, the data presented indicate that no strong barriers to gene flow exists between riverine tsetse populations in adjacent river basins, especially so for G. tachinoides. Conclusions/Significance: Therefore, potential re-invasion of flies from adjacent river basins will have to be prevented by establishing buffer zones between the Mouhoun and the other river basin(s), in the framework of the PATTEC (Pan African Tsetse and Trypanosomosis Eradication Campaign) eradication project that is presently targeting the northern part of the Mouhoun River Basin. We argue that these genetic analyses should always be part of the baseline data collection before any tsetse control project is initiated.