Genetically, Rhizobium sp. strain NGR234 and R. fredii USDA257 are closely related. Small differences in their nodulation genes result in NGR234 secreting larger amounts of more diverse lipo-oligosaccharidic Nod factors than USDA257. What effects these differences have on nodulation were analyzed by inoculating 452 species of legumes, representing all three subfamilies of the Leguminosae, as well as the nonlegume Parasponia andersonii, with both strains. The two bacteria nodulated P. andersonii, induced ineffective outgrowths on Delonix regia, and nodulated Chamaecrista fasciculata, a member of the only nodulating genus of the Caesalpinieae tested. Both strains nodulated a range of mimosoid legumes, especially the Australian species of Acacia, and the tribe Ingeae. Highest compatibilities were found with the papilionoid tribes Phaseoleae and Desmodieae. On Vigna spp. (Phaseoleae), both bacteria formed more effective symbioses than rhizobia of the “cowpea” (V. unguiculata) miscellany. USDA257 nodulated an exact subset (79 genera) of the NGR234 hosts (112 genera). If only one of the bacteria formed effective, nitrogen-fixing nodules it was usually NGR234. The only exceptions were with Apios americana, Glycine max, and G. soja. Few correlations can be drawn between Nod-factor substituents and the ability to nodulate specific legumes. Relationships between the ability to nodulate and the origin of the host were not apparent. As both P. andersonii and NGR234 originate from Indonesia/Malaysia/Papua New Guinea, and NGR234's preferred hosts (Desmodiinae/ Phaseoleae) are largely Asian, we suggest that broad host range originated in Southeast Asia and spread outward.