The genus Bartonella comprises facultative intracellular bacteria with a unique lifestyle. After transmission by blood-sucking arthropods they colonize the erythrocytes of mammalian hosts causing acute and chronic infectious diseases. Although the pathogen-host interaction is well understood, little is known about the evolutionary origin of the infection strategy manifested by Bartonella species. Here we analyzed six genomes of Bartonella apis, a honey bee gut symbiont that to date represents the closest relative of pathogenic Bartonella species. Comparative genomics revealed that B. apis encodes a large set of vertically inherited genes for amino acid and cofactor biosynthesis and nitrogen metabolism. Most pathogenic bartonellae have lost these ancestral functions, but acquired specific virulence factors and expanded a vertically inherited gene family for harvesting cofactors from the blood. However, the deeply rooted pathogen Bartonella tamiae has retained many of the ancestral genome characteristics reflecting an evolutionary intermediate state toward a host-restricted intraerythrocytic lifestyle. Our findings suggest that the ancestor of the pathogen Bartonella was a gut symbiont of insects and that the adaptation to blood-feeding insects facilitated colonization of the mammalian bloodstream. This study highlights the importance of comparative genomics among pathogens and non-pathogenic relatives to understand disease emergence within an evolutionary-ecological framework.