Glossina fuscipes fuscipes Newstead 1910 (Diptera: Glossinidae) is the primary vector of human sleeping sickness in Kenya and Uganda. This is the first report on its population structure. A total of 688 nucleotides of mitochondrial ribosomal 16S2 and cytochrome oxidase I genes were sequenced. Twenty-one variants were scored in 79 flies from three geographically diverse natural populations. Four haplotypes were shared among populations, eight were private and nine were singletons. The mean haplotype and nucleotide diversities were 0.84 and 0.009, respectively. All populations were genetically differentiated and were at demographic equilibrium. In addition, a longstanding laboratory culture originating from the Central African Republic (CAR-lab) in 1986 (or before) was examined. Haplotype and nucleotide diversities in this culture were 0.95 and 0.012, respectively. None of its 27 haplotypes were shared with the East African populations. A first approximation of relative effective population sizes was Uganda > CAR-lab > Kenya. It was concluded that the structure of G. f. fuscipes populations in East Africa is localized.