Rhizobia are a phylogenetically diverse group of alpha and beta proteobacteria capable of infecting legume roots and forming a nitrogen-fixing symbiosis. In Australian agriculture, this symbiosis is harnessed to supply bioavailable nitrogen to soils by including pulse or pasture legumes in rotation with cereals. Rhizobia compatible with agricultural legumes are not naturally present in Australian soils, so exotic and highly effective strains are introduced as inoculants to maximise the benefits of legumes in rotations. Over time, genetically diverse populations of naturalized rhizobia have established in Australian soils and in some areas, they exist in such high abundance that they out-compete the inoculant to nodulate the target legume. A key driver for emergence of naturalised rhizobia is horizontal transfer of symbiosis genes from inoculants to soil bacteria, which are encoded on mobile genetic elements. For rhizobia in the genus Mesorhizobium, symbiosis genes are chromosomally encoded on genomic islands called symbiosis Integrative and Conjugative Elements (ICEs). Symbiosis ICEs can excise from the inoculant chromosome, transferring to a recipient cell by conjugation, and integrate into the chromosome at specific conserved sequences, resulting in a new symbiotic strain. In the environment, ICE recipients appear to be saprophytic non-symbiotic Mesorhizobium spp. that are present in soils as natural members of the microbiome. Crucially, while symbiosis ICE recipients can nodulate legume hosts, they may not fix nitrogen efficiently, even though the symbiosis ICE was acquired from a highly effective inoculant strain. This suggests an interaction between the core and symbiosis ICE accessory genome exists in rhizobia, which can significantly influence nitrogen fixation efficiency. Where large populations of suboptimally effective novel strains develop, this can pose a significant constraint to maximising symbiotic nitrogen fixation.