A strictly host-dependent lifestyle has profound evolutionary consequences for bacterial genomes. Most prominent is a sometimes-dramatic amount of gene loss and genome reduction. Recently, highly reduced genomes from the co-resident intracellular symbionts of sharpshooters were shown to exhibit a striking level of metabolic interdependence. One symbiont, called Sulcia muelleri (Bacteroidetes), can produce eight of the 10 essential amino acids, despite having a genome of only 245 kb. The other, Baumannia cicadellinicola (gamma-Proteobacteria), can produce the remaining two essential amino acids as well as many vitamins. Cicadas also contain the symbiont Sulcia, but lack Baumannia and instead contain the co-resident symbiont Hodgkinia cicadicola (alpha-Proteobacteria). Here we report that, despite at least 200 million years of divergence, the two Sulcia genomes have nearly identical gene content and gene order. Additionally, we show that despite being phylogenetically distant and drastically different in genome size and architecture, Hodgkinia and Baumannia have converged on gene sets conferring similar capabilities for essential amino acid biosynthesis, in both cases precisely complementary to the pathways conserved in Sulcia. In contrast, they have completely divergent capabilities for vitamin biosynthesis. Despite having the smallest gene set known in bacteria, Hodgkinia devotes at least 7% of its proteome to cobalamin (vitamin B(12)) biosynthesis, a significant metabolic burden. The presence of these genes can be explained by Hodgkinia's retention of the cobalamin-dependent version of methionine synthase instead of the cobalamin-independent version found in Baumannia, a situation that necessitates retention of cobalamin biosynthetic capabilities to make the essential amino acid methionine.