Horizontal gene transfer (HGT) is an important mode of adaptation and diversification of prokaryotes and eukaryotes and a major event underlying the emergence of bacterial pathogens and mutualists. Yet it remains unclear how complex phenotypic traits such as the ability to fix nitrogen with legumes have successfully spread over large phylogenetic distances. Here we show, using experimental evolution coupled with whole genome sequencing, that co-transfer of imuABC error-prone DNA polymerase genes with key symbiotic genes accelerates the evolution of a soil bacterium into a legume symbiont. Following introduction of the symbiotic plasmid of Cupriavidus taiwanensis, the Mimosa symbiont, into pathogenic Ralstonia solanacearum we challenged transconjugants to become Mimosa symbionts through serial plant-bacteria co-cultures. We demonstrate that a mutagenesis imuABC cassette encoded on the C. taiwanensis symbiotic plasmid triggered a transient hypermutability stage in R. solanacearum transconjugants that occurred before the cells entered the plant. The generated burst in genetic diversity accelerated symbiotic adaptation of the recipient genome under plant selection pressure, presumably by improving the exploration of the fitness landscape. Finally, we show that plasmid imuABC cassettes are over-represented in rhizobial lineages harboring symbiotic plasmids. Our findings shed light on a mechanism that may have facilitated the dissemination of symbiotic competency among a-and b-proteobacteria in natura and provide evidence for the positive role of environment-induced mutagenesis in the acquisition of a complex lifestyle trait. We speculate that co-transfer of complex phenotypic traits with mutagenesis determinants might frequently enhance the ecological success of HGT.