Many of the alpha-proteobacteria establish long-term, often chronic, interactions with higher eukaryotes. These interactions range from pericellular colonization through facultative intracellular multiplication to obligate intracellular lifestyles. A common feature in this wide range of interactions is modulation of host-cell proliferation, which sometimes leads to the formation of tumour-like structures in which the bacteria can grow. Comparative genome analyses reveal genome reduction by gene loss in the intracellular alpha-proteobacterial lineages, and genome expansion by gene duplication and horizontal gene transfer in the free-living species. In this review, we discuss alpha-proteobacterial genome evolution and highlight strategies and mechanisms used by these bacteria to infect and multiply in eukaryotic cells.