Gene transfer agents (GTAs) are domesticated viral particles that mediate horizontal transfer of small random segments of chromosomal DNA between prokaryotic cells. Recently, it was discovered that pathogens of the genus Bartonella contain a conserved phage-derived gene cluster for a novel GTA, which is physically separated from another phage-derived cluster that replicates the surrounding genomic regions in a process called run-off replication. Together, these two loci became a key innovation facilitating the adaptive radiation of Bartonella by efficiently transferring adaptive genes between cells. How GTAs evolve from ancestral phages has remained elusive. To study the origin and evolution of the Bartonella GTA, we sequenced the closest known relatives to the Bartonella group, symbionts of ants and bees, and performed comparative and evolutionary analyses with Bartonella genomes. We discovered that the GTA genes co-diversify with the host genomes, in contrast to other GTA-like lineages, which evolve like phages capable of horizontal descent. Interestingly, we found that the GTA genes were already present in the Bartonella last common ancestor, while the gene cluster causing run-off replication was acquired later. Therefore, although transfer of random DNA fragments probably took place early on, it is plausible that the targeted sharing of a genomic island enriched in genes for host association caused the Bartonella radiation, leading to the infection of a wide range of mammalian hosts. With this work we propose a model for the gradual transformation of a prophage into a specialised GTA in a process driven by selection from the host bacterial genome.