Hairy vetch (Vicia villosa Roth) is a leguminous crop widely used as green manure and a cover crop in Japan. It exhibits strong weed-suppressing activity, high resistance to insect pests, and the ability to fix nitrogen through symbiotic interactions with soil bacteria known as rhizobia. Few studies have investigated the rhizobia that form nodules on hairy vetch in Japan, and the biological resources available for selecting high nitrogen-fixing rhizobia are limited. In the present study, we isolated 110 hairy vetch rhizobia from 13 different areas in Japan. Based on their 16S rRNA gene sequences, 73% of the isolates were identified as Rhizobium leguminosarum. A comparative analysis of nodC and 16S rRNA gene phylogenies revealed that several isolates possessed congruent nodC sequences despite having divergent 16S rRNA gene sequences, suggesting that the horizontal transfer of nod genes occurred during the evolution of rhizobia. Inoculation tests showed that isolates closely related to R. leguminosarum had better plant growth-promoting effects than other strains, thereby providing a promising agricultural resource for inoculating crops.