Horsegram [Macrotyloma uniflorum (Lam.) Verdc.) is an important grain legume and fodder crop in India. Information on root nodule endosymbionts of this legume in India is limited. In the present study, 69 isolates from naturally occurring root nodules of horsegram collected from two agro-eco-climatic regions of South India was analyzed by generation rate, acid/alkali reaction on YMA medium, restriction fragment length polymorphism analysis of 16S-23S rDNA intergenic spacer region (IGS), and sequence analyses of IGS and housekeeping genes glnII and recA. Based on the rDNA IGS RFLP by means of three restriction enzymes rhizobia were grouped in five clusters (I–V). By sequence analysis of 16S-23S rDNA IGS identified genotypes of horsegram rhizobia were distributed into five divergent lineages of Bradyrhizobium genus which comprised (I) the IGS type IV rhizobia and valid species B. yuanmingense, (II) the strains of IGS type I and Bradyrhizobium sp. ORS 3257 isolated from Vigna sp., (III) the strains of the IGS type II and Bradyrhizobium sp. CIRADAc12 from Acacia sp., (IV) the IGS type V strains and Bradyrhizobium sp. genospecies IV, and (V) comprising genetically distinct IGS type III strains which probably represent an uncharacterized new genomic species. Nearly, 87% of indigenous horsegram isolates (IGS types I, II, III, and V) could not be related to any other species within the genus Bradyrhizobium. Phylogeny based on housekeeping glnII and recA genes confirmed those results found by the analysis of the IGS sequence. All the isolated rhizobia nodulated Macrotyloma sp. and Vigna spp., and only some of them formed nodules on Arachis hypogeae. The isolates within each IGS type varied in their ability to fix nitrogen. Selection for high symbiotic effective strains could reward horsegram production in poor soils of South India where this legume is largely cultivated.