Mesorhizobia are soil bacteria that establish nitrogen-fixing symbioses with various legumes. Novel symbiotic mesorhizobia frequently evolve following horizontal transfer of symbiosis-gene-carrying integrative and conjugative elements (ICESyms) to indigenous mesorhizobia in soils. Evolved symbionts exhibit a wide range in symbiotic effectiveness, with some fixing nitrogen poorly or not at all. Little is known about the genetic diversity and symbiotic potential of indigenous soil mesorhizobia prior to ICESym acquisition. We sequenced genomes of Mesorhizobium spp. strains cultured directly from cultivated and uncultivated Australian soils. Of these, most lacked symbiosis genes. The only isolated symbiotic strains were either exotic strains used previously as legume inoculants, or indigenous mesorhizobia that had acquired exotic ICESyms. No native symbiotic strains were identified. Indigenous nonsymbiotic strains formed 22 genospecies with phylogenomic diversity overlapping the diversity of internationally isolated symbiotic Mesorhizobium spp. The genomes of indigenous mesorhizobia exhibited no evidence of prior involvement in nitrogen-fixing symbiosis, yet their core genomes were similar to symbiotic strains. Genomes of nonsymbiotic mesorhizobia harboured similar mobile elements to those of symbiotic mesorhizobia, including ICESym-like elements but lacking symbiosis genes. Diverse indigenous isolates receiving ICESyms through horizontal gene transfer formed effective symbioses with Lotus and Biserrula legumes, indicating most nonsymbiotic mesorhizobia have an innate capacity for nitrogen-fixing symbiosis following ICESym acquisition. Non-fixing ICESym-harbouring strains were isolated sporadically within species alongside effective symbionts, indicating chromosomal lineage does not predict symbiotic potential. Our observations suggest previously observed genomic diversity amongst symbiotic Mesorhizobium spp. represents a fraction of the extant diversity of nonsymbiotic strains. The overlapping phylogeny of symbiotic and nonsymbiotic clades suggests major clades of Mesorhizobium diverged prior to introduction of symbiosis genes and therefore chromosomal genes involved in symbiosis have evolved largely independent of nitrogen-fixing symbiosis.