Symbiosis is often characterized by co-evolutionary changes in the genomes of the partners involved. An understanding of these changes can provide insight into the nature of the relationship, including the mechanisms that initiate and maintain an association between organisms. In this study we examined the genome sequences of bacteria isolated from the Drosophila melanogaster gut with the objective of identifying genes that are important for function in the host. We compared microbiota isolates with con-specific or closely related bacterial species isolated from non-fly environments. First the phenotype of germ-free Drosophila (axenic flies) was compared to that of flies colonized with specific bacteria (gnotobiotic flies) as a measure of symbiotic function. Non-fly isolates were functionally distinct from bacteria isolated from flies, conferring slower development and an altered nutrient profile in the host, traits known to be microbiota-dependent. Comparative genomic methods were next employed to identify putative symbiosis factors: genes found in bacteria that restore microbiota-dependent traits to gnotobiotic flies, but absent from those that do not. Factors identified include riboflavin synthesis and stress resistance. We also used a phylogenomic approach to identify protein coding genes for which fly-isolate sequences were more similar to each other than to other sequences, reasoning that these genes may have a shared function unique to the fly environment. This method identified genes in Acetobacter species that cluster in two distinct genomic loci: one predicted to be involved in oxidative stress detoxification and another encoding an efflux pump. In summary, we leveraged genomic and in vivo functional comparisons to identify candidate traits that distinguish symbiotic bacteria. These candidates can serve as the basis for further work investigating the genetic requirements of bacteria for function and persistence in the Drosophila gut.