Nitrogen (N), the nutrient most required for plant growth, is key for good yield of agriculturally important crops. Common bean (Phaseolus vulgaris L.) can benefit from bacteria collectively called rhizobia, which are capable of fixing atmospheric nitrogen (N2) in root nodules and supplying it to the plant. Common bean is amongst the most promiscuous legume hosts; several described species, in addition to putative novel ones have been reported as able to nodulate this legume, although not always effectively in terms of fixing N2. In this study, we present data indicating that Brazilian strains PRF 35T, PRF 54, CPAO 1135 and H 52, currently classified as Rhizobium tropici, represent a novel species symbiont of common bean. Morphological, physiological and biochemical properties differentiate these strains from other species of the genus Rhizobium, as do BOX-PCR profiles (less than 60% similarity), multilocus sequence analysis with recA, gyrB and rpoA (less than 96.4% sequence similarity), DNA-DNA hybridization (less than 50% DNA-DNA relatedness), and average nucleotide identity of whole genomes (less than 92.8.%). The novel species is effective in nodulating and fixing N2 with P. vulgaris, Leucaena leucocephala and Leucaena esculenta. We propose the name Rhizobium paranaense sp. nov. for this novel taxon, with strain PRF 35T (=CNPSo 120T=LMG 27577T=IPR-Pv 1249T) as the type strain.