Acetic acid bacteria (AAB) live in sugar rich environments, including food matrices, plant tissues, and the gut of sugar-feeding insects. By comparing the newly sequenced genomes of Asaia platycodi and Saccharibacter sp., symbionts of Anopheles stephensi and Apis mellifera, respectively, with those of 14 other AAB,we provide a genomic view of the evolutionary pattern of this bacterial group and clues on traits that explain the success of AAB as insect symbionts. A specific pre-adaptive trait, cytochrome bo3 ubiquinol oxidase, appears ancestral inAABandshows aphylogeny that iscongruent with thatof thegenomes.The functional properties of this terminal oxidase might have allowed AAB to adapt to the diverse oxygen levels of arthropod guts.