Leaves of the wild yam species Dioscorea sansibarensis display prominent forerunner or “drip” tips filled with extracellular bacteria of the species Orrella dioscoreae.1 This species of yam is native to Madagascar and tropical Africa and reproduces mainly asexually through aerial bulbils and underground tubers, which also contain a small population of O. dioscoreae.2,3 Despite apparent vertical transmission, the genome of O. dioscoreae does not show any of the hallmarks of genome erosion often found in hereditary symbionts (e.g., small genome size and accumulation of pseudogenes).4, 5, 6 We investigated here the range and distribution of leaf symbiosis between D. sansibarensis and O. dioscoreae using preserved leaf samples from herbarium collections that were originally collected from various locations in Africa. We recovered DNA from the extracellular symbiont in all samples, showing that the symbiosis is widespread throughout continental Africa and Madagascar. Despite the degraded nature of this DNA, we constructed 17 symbiont genomes using de novo methods without relying on a reference. Phylogenetic and genomic analyses revealed that horizontal transmission of symbionts and horizontal gene transfer have shaped the evolution of the symbiont. These mechanisms could help explain lack of signs of reductive genome evolution despite an obligate host-associated lifestyle. Furthermore, phylogenetic analysis of D. sansibarensis based on plastid genomes revealed a strong geographical clustering of samples and provided evidence that the symbiosis originated at least 13 mya, earlier than previously estimated.3