Phylogenetic analyses of 16S rRNA support close relationships between the Gammaproteobacteria Sodalis glossinidius, a tsetse (Diptera: Glossinidae) symbiont, and bacteria infecting diverse insect orders. To further examine the evolutionary relationships of these Sodalis-like symbionts, phylogenetic trees were constructed for a subset of putative surface-encoding genes (i.e. ompA, spr, slyB, rcsF, ycfM, and ompC). The ompA and ompC loci were used towards examining the intra- and interspecific diversity of Sodalis within tsetse, respectively. Intraspecific analyses of ompA support elevated nonsynonymous (dN) polymorphism with an excess of singletons, indicating diversifying selection, specifically within the tsetse Glossina morsitans. Additionally, interspecific ompC comparisons between Sodalis and Escherichia coli demonstrate deviation from neutrality, with higher fixed dN observed at sites associated with extracellular loops. Surface-encoding genes varied in their phylogenetic resolution of Sodalis and related bacteria, suggesting conserved versus host specific roles. Moreover, Sodalis and its close relatives exhibit genetic divergence at the rcsF, ompA and ompC loci, indicative of initial molecular divergence. The application of outer membrane genes as markers for further delineating the systematics of recently diverged bacteria is discussed. These results increase our understanding of insect symbiont evolution, while also identifying early genome alterations occurring upon integration of microbes with eukaryotic hosts.