The alpha-proteobacteria, from which mitochondria are thought to have originated, display a 10-fold genome size variation and provide an excellent model system for studies of genome size evolution in bacteria. Here, we use computational approaches to infer ancestral gene sets and to quantify the flux of genes along the branches of the alpha-proteobacterial species tree. Our study reveals massive gene expansions at branches diversifying plant-associated bacteria and extreme losses at branches separating intracellular bacteria of animals and humans. Alterations in gene numbers have mostly affected functional categories associated with regulation, transport, and small-molecule metabolism, many of which are encoded by paralogous gene families located on auxiliary chromosomes. The results suggest that the alpha-proteobacterial ancestor contained 3,000-5,000 genes and was a free-living, aerobic, and motile bacterium with pili and surface proteins for host cell and environmental interactions. Approximately one third of the ancestral gene set has no homologs among the eukaryotes. More than 40% of the genes without eukaryotic counterparts encode proteins that are conserved among the alpha-proteobacteria but for which no function has yet been identified. These genes that never made it into the eukaryotes but are widely distributed in bacteria may represent bacterial drug targets and should be prime candidates for future functional characterization.