Agromonas oligotrophica (Bradyrhizobium oligotrophicum) S58T is a nitrogen-fixing oligotrophic bacterium isolated from paddy field soil that is able to grow in extra-low-nutrient environments. Here, the complete genome sequence of S58 was determined. The S58 genome was found to comprise a circular chromosome of 8,264,165 bp with an average GC content of 65.1% lacking nodABC genes and the typical symbiosis island. The genome showed a high level of similarity to the genomes of Brady-rhizobium sp. ORS278 and Bradyrhizobium sp. BTAi1, including nitrogen fixation and photosynthesis gene clusters, which nodulate an aquatic legume plant, Aeschynomene indica, in a Nod factor-independent manner. Although nonsymbiotic (brady)rhizobia are significant components of rhizobial populations in soil, we found that most genes important for nodule development (ndv) and symbiotic nitrogen fixation (nif and fix) with A. indica were well conserved between the ORS278 and S58 genomes. Therefore, we performed inoculation experiments with five A. oligotrophica strains (S58, S42, S55, S72, and S80). Surprisingly, all five strains of A. oligotrophica formed effective nitrogen-fixing nodules on the roots and/or stems of A. indica, with differentiated bacteroids. Nonsymbiotic (brady)rhizobia are known to be significant components of rhizobial populations without a symbiosis island or symbiotic plasmids in soil, but the present results indicate that soil-dwelling A. oligotrophica generally possesses the ability to establish symbiosis with A. indica. Phylogenetic analyses suggest that Nod factor-independent symbiosis with A. indica is a common trait of nodABC- and symbiosis island-lacking strains within the members of the photosynthetic Bradyrhizobium clade, including A. oligotrophica.