Bacterial integrative & conjugative elements (ICEs) are chromosomally-integrated DNA islands that excise to form circular molecules capable of self-transmission via conjugation. Lateral transfer of an ICE subgroup, termed symbiosis-islands, converts non-symbiotic Mesorhizobium spp. into nitrogen-fixing plant symbionts in a single evolutionary step. Here we describe the discovery of a novel “tripartite” ICE-form, which exist as three separate chromosomally-integrated DNA segments that recombine and horizontally transfer as a single circular element. Genome sequence comparisons of Biserrula pelecinus-nodulating strain Mesorhizobium ciceri WSM1271 with environmental and laboratory-isolated symbiosis-island exconjugants revealed that three distinct DNA regions were transferred from WSM1271 during conjugation. Using mutagenesis, quantitative PCR and artificial “mini-ICE” elements, we have confirmed that the tripartite ICE, ICEMcSym1271, encodes three site-specific recombinases that catalyse recombination between three distinct pairs of DNA attachment sites (att) located at each ICEMcSym1271-chromosome junction. The position and orientation of each att site is such that the sequential action of each recombinase in any order should resolve ICEMcSym1271 into a single circular ICE. Through quantitative PCR we have demonstrated that recombination of each of three att-site pairs is coordinated and is additionally co-stimulated by the quorum-sensing regulator TraR. Distinct tripartite ICEs have been identified in other Biserrula and Lotus-nodulating species, and horizontal transfer of these tripartite ICEs has also been demonstrated in the laboratory. In each case, transfer confers on the recipient an ability to form a specific symbiotic relationship with the legume species associated with the donor Mesorhizobium. These discoveries highlight the great diversity, peculiarity and plasticity of mobile elements and clearly illustrate that non-canonical mobile genetic elements remain uncharacterised in bacterial genomes.