Common bean [Phaseolus vulgaris (Linnaeus)] is the key source of protein, carbohydrates and micronutrients for over 300 million people in the tropics. Like many legumes, P. vulgaris can fix atmospheric nitrogen in symbiosis with rhizobia, alleviating the need for the expensive and polluting N-fertilizers. The crop is known to nodulate with a wide range of rhizobia and, although Brazil is not a center of genetic origin/domestication of P. vulgaris, a variety of rhizobial species have been found as symbionts of the legume. Mato Grosso do Sul (MS) is one of the largest common bean producer states in Brazil, with reports of high yields and abundant natural nodulation. The objective of this study was to evaluate the diversity of 73 indigenous rhizobia isolated from common bean grown in 22 municipalities of MS. Great morphophysiological and genetic diversity was found, as indicated by the six and 35 clusters formed, considering the similarity level of 75 and 70%, respectively, for the phenotypic and rep-PCR dendrograms. Eleven representative isolates were selected for detailed genetic characterization using 16S rRNA and three protein-coding housekeeping genes, glnII, gyrB and recA. We identified species originated from the centers of origin/domestication of the legume, R. etli and R. phaseoli, species probably indigenous of Brazil, R. leucaenae and others of the Rhizobium/Agrobacterium clade, in addition to putative new species. The results highlight the great rhizobial diversity of the region.