Host-associated microbial interactions may involve genome complementation, driving-enhanced communal efficiency and stability. The tsetse fly (Diptera: Glossinidae), the obligate vector of African trypanosomes (Trypanosoma brucei subspp.), harbours two enteric Gammaproteobacteria symbionts: Wigglesworthia glossinidia and Sodalis glossinidius. Host coevolution has streamlined the Wigglesworthia genome to complement the exclusively sanguivorous tsetse lifestyle. Comparative genomics reveal that the Sodalis genome contains the majority of Wigglesworthia genes. This significant genomic overlap calls into question why tsetse maintains the coresidence of both symbionts and, furthermore, how symbiont homeostasis is maintained. One of the few distinctions between the Wigglesworthia and Sodalis genomes lies in thiamine biosynthesis. While Wigglesworthia can synthesize thiamine, Sodalis lacks this capability but retains a thiamine ABC transporter (tbpAthiPQ) believed to salvage thiamine. This genetic complementation may represent the early convergence of metabolic pathways that may act to retain Wigglesworthia and evade species antagonism. We show that thiamine monophosphate, the specific thiamine derivative putatively synthesized by Wigglesworthia, impacts Sodalis thiamine transporter expression, proliferation and intracellular localization. A greater understanding of tsetse symbiont interactions may generate alternative control strategies for this significant medical and agricultural pest, while also providing insight into the evolution of microbial associations within hosts.