Rhizobium fredii USDA257 is a Gram-negative soil bacterium from China that fixes nitrogen in symbiosis with primitive soybean (Glycine max [L.] Merr.) cultivars such as Peking, but not with advanced cultivars such as McCall. Mutation of either of two bacterial loci, nolBTUVWX or nolC, removes this cultivar-specificity constraint, allowing the bacterium to nodulate advanced cultivars. We have discovered that USDA257 forms nodules on Erythrina costaricensis M. Micheli, but not on six other species of this genus, which includes trees and shrubs from the tropics. Inactivation of nolBU or nolC broadens the symbiosis to include other Erythrina species. Whereas nolBU-mutants acquire the capacity to nodulate E. fusca Loureiro, E. variegata L., and E. vespertilio Benth., nolC-mutants could nodulate only E. variegata. Nodules are determinate and often clustered in root axils near the root crown. E. variegata nodules containing a nolBU-mutant consist of well-developed inner and outer cortical layers, as well as a bacteroid zone. The cortical layers are separated from one another by a meristematic region that is associated with large darkly staining cells, and cells of the inner cortex contain numerous starch grains. Histochemical staining of E. variegata roots inoculated with a strain containing a nolB-lacZ gene fusion confirms that nolB and nolC are expressed during the initial stages of bacterial interaction with the host. R. fredii enters elongated root-hairs via infection threads, which ramify within root-hairs and are associated with meristematic activity in the adjacent underlying cortical cells.