Vertical transmission of obligate symbionts generates a predictable evolutionary history of symbionts that reflects that of their hosts. In insects, evolutionary associations between symbionts and their hosts have been investigated primarily among species, leaving population-level processes largely unknown. In this study, we investigated the tsetse (Diptera: Glossinidae) bacterial symbiont, Wigglesworthia glossinidia, to determine whether observed codiversification of symbiont and tsetse host species extends to a single host species (Glossina fuscipes fuscipes) in Uganda. To explore symbiont genetic variation in G. f. fuscipes populations, we screened two variable loci (lon and lepA) from the Wigglesworthia glossinidia bacterium in the host species Glossina fuscipes fuscipes (W. g. fuscipes) and examined phylogeographic and demographic characteristics in multiple host populations. Symbiont genetic variation was apparent within and among populations. We identified two distinct symbiont lineages, in northern and southern Uganda. Incongruence length difference (ILD) tests indicated that the two lineages corresponded exactly to northern and southern G. f. fuscipes mitochondrial DNA (mtDNA) haplogroups (P = 1.0). Analysis of molecular variance (AMOVA) confirmed that most variation was partitioned between the northern and southern lineages defined by host mtDNA (85.44%). However, ILD tests rejected finer-scale congruence within the northern and southern populations (P = 0.009). This incongruence was potentially due to incomplete lineage sorting that resulted in novel combinations of symbiont genetic variants and host background. Identifying these novel combinations may have public health significance, since tsetse is the sole vector of sleeping sickness and Wigglesworthia is known to influence host vector competence. Thus, understanding the adaptive value of these host-symbiont combinations may afford opportunities to develop vector control methods.