Buchnera is a mutualistic intracellular symbiont of aphids. Their association began about 200 million years ago, with host and symbiont lineages evolving in parallel since that time. During this coevolutionary process, Buchnera has experienced a dramatic decrease of genome size, retaining only essential genes for its specialized lifestyle. Previous studies reported that genome size in Buchnera spp. is very uniform, suggesting that genome shrinkage occurred early in evolution, and that modern lineages retain the genome size of a common ancestor. Our physical mapping of Buchnera genomes obtained from five aphid lineages shows that the genome size is not conserved among them, but has been reduced down to 450 kb in some species. Here we show evidence of six species with a genome size smaller than Mycoplasma genitalium, the smallest bacterial genome reported thus far (580 kb). Our findings strongly suggest that the Buchnera genome is still experiencing a reductive process toward a minimum set of genes necessary for its symbiotic lifestyle.