The tsetse fly, Glossina morsitans morsitans, is a significant problem in Zambia and Malawi. It is the vector for the human infective parasite Trypanosoma brucei rhodesiense, which causes human African trypanosomiasis, and various Trypanosoma species, which cause African animal trypanosomiasis. Understanding the genetic diversity and population structure of G. m. morsitans is the basis of elucidating the connectivity of the tsetse fly populations, information that is essential in implementing successful tsetse fly control activities. This study conducted a population genetic study using partial mitochondrial cytochrome oxidase gene 1 (CO1) and 10 microsatellite loci to investigate the genetic diversity and population structure of G. m. morsitans captured in the major HAT foci in Zambia and Malawi. We have included 108 and 99 G. m. morsitans samples for CO1 and microsatellite analyses respectively. Our results suggest the presence of two different genetic clusters of G. m. morsitans, existing East and West of the escarpment of the Great Rift Valley. We have also revealed genetic similarity between the G. m. morsitans in Kasungu National Park and those in the Luangwa river basin in Zambia, indicating that this population should also be included in this historical tsetse belt. Although further investigation is necessary to illustrate the whole picture in East and Southern Africa, this study has extended our knowledge of the population structure of G. m. morsitans in Southern Africa.