Sodalis glossinidius is a maternally transmitted secondary endosymbiont residing intracellularly in tissues of the tsetse flies, Glossina spp. In this study, we have used Tn5 mutagenesis and a negative selection procedure to derive a S. glossinidius mutant that is incapable of invading insect cells in vitro and is aposymbiotic when microinjected into tsetse. This mutant strain harbors Tn5 integrated into a chromosomal gene sharing high sequence identity with a type III secretion system invasion gene (invC) previously identified in Salmonella enterica. With the use of degenerate PCR, we have amplified a further six Sodalis inv/spa genes sharing high sequence identity with type III secretion system genes encoded by Salmonella pathogenicity island 1. Phylogenetic reconstructions based on the inv/spa genes of Sodalis and other members of the family Enterobacteriaceae have consistently identified a well-supported clade containing Sodalis and the enteric pathogens Shigella and Salmonella. These results suggest that Sodalis may have evolved from an ancestor with a parasitic intracellular lifestyle, possibly a latter-day entomopathogen. These observations lend credence to a hypothesis suggesting that vertically transmitted mutualistic endosymbionts evolve from horizontally transmitted parasites through a parasitism-mutualism continuum.