Integrative and conjugative elements (ICEs) are one of the most prevalent but least-characterised families of mobile genetic elements in bacteria. We have identified a family of ICEs that exists as three separate parts integrated within the single chromosomes of symbiotic mesorhizobia. These “tripartite ICEs,” through a series of chromosomal recombinations mediated by integrase proteins, assemble into a single circular ICE prior to conjugative transfer. Following transfer to nonsymbiotic mesorhizobia, tripartite ICEs integrate and disassemble into three parts in the recipient genome and exconjugant mesorhizobia gain the ability to form a symbiosis with legumes. The unheralded existence of tripartite ICEs raises the possibility that multipartite elements may reside in other organisms, but have been overlooked because of their unusual biology. Thus these discoveries expand our appreciation of the potential for gene transfer in bacteria and demonstrate how mobile genetic elements can dramatically manipulate the bacterial genome.