While the occurrence of Betaproteobacteria occupying the nodules of tropical legumes has been shown, little is known about subtropical areas. Araucaria Forest is a subtropical endangered ecosystem, and a better understanding of the legume-rhizobial symbionts may allow their use in land reclamation. The 16S rRNA gene of bacteria isolated from nine leguminous species was sequenced and their nodulation tested in Mimosa scabrella and Phaseolus vulgaris. 196 isolates were identified as eight genotypes: Pantoea, Pseudomonas, Bradyrhizobium sp1-2, Rhizobium, and Burkholderia sp1-3. The majority of the isolates from native plants (87 %) were taxonomically related to β-rhizobia, namely Burkholderia, however the legumes Galactia crassifolia and Collea speciosa were nodulated by both α and β-rhizobia, and Acacia dealbata, an exotic plant, only by α-rhizobia. The nifH genes of some isolates were sequenced and N-fixing potential shown by the acetylene reduction test. Most of the isolates nodulated the test plants, some were effective in M. scabrella, but all presented low efficiency in the exotic promiscuous legume P. vulgaris. Pantoea and Pseudomonas did not nodulate and probably are endophytic bacteria. The presented data shows diversity of α, β and γ-Proteobacteria in nodules of subtropical legumes, and suggests host specificity with β-rhizobia. Potential isolates were found for M. scabrella, indicating that a high N-fixing strain may be further inoculated in plants for use in reforestation.