Rhizobia are soil bacteria that can establish nitrogen-fixing symbioses with legumes. In Mesorhizobium spp. genes for symbiosis are often located on integrative and conjugative elements (ICESyms), which transfer to indigenous mesorhizobia in soils. While this phenomenon is documented for symbionts of Lotus, Cicer and Biserrula, little is understood about the diversity and symbiotic potential of indigenous soil mesorhizobia. Here we isolated and sequenced genomes of 144 mesorhizobia cultured from cultivated and uncultivated Australian soils. Of these, 126 were nonsymbiotic Mesorhizobium spp. (NS-meso), while the remaining were introduced inoculant strains or NS-meso carrying ICESyms transferred from inoculants. NS-meso formed 22 genospecies with diversity overlapping previously-isolated symbiotic Mesorhizobium spp. and extending the genus by 15 genospecies. The NS-meso core-genome was similar to that of symbiotic strains and NS-meso harboured similar mobile elements, including a tripartite ICE related to the ancestor of tripartite ICESyms but lacking symbiosis genes. Gene content of NS-mesos provided no evidence for prior involvement in nitrogen-fixing symbioses; however, the core gene content of NS-meso suggests an innate capacity to form symbiosis following ICESym acquisition. Diverse ICESym-exconjugants isolated from soil, nodules and laboratory transfer formed effective symbioses with Lotus and Biserrula. We propose isolated nonsymbiotic Mesorhizobium populations resemble those extant prior to the evolution of nitrogen-fixing symbiosis in this genus and that symbiotic strains represent a minority of extant Mesorhizobium. These findings highlight the remarkable single-step evolution of nitrogen-fixing symbiosis through ICESym transfer and suggest Mesorhizobium core-chromosome genes involved in symbiosis have evolved largely independent of nitrogen-fixing symbiosis.