We explored the genetic basis of the promiscuous symbiosis of Sophora flavescens with diverse rhizobia. To determine the impact of Nod factors (NFs) on the symbiosis of S. flavescens, nodulation-related gene mutants of representative rhizobial strains were generated. Strains with mutations in common nodulation genes (nodC, nodM, and nodE) failed to nodulate S. flavescens, indicating that the promiscuous nodulation of this plant is strictly dependent on the basic NF structure. Mutations of the NF decoration genes nodH, nodS, nodZ, and noeI did not affect the nodulation of S. flavescens, but these mutations affected the nitrogen-fixation efficiency of nodules. Wild-type Bradyrhizobium diazoefficiens USDA110 cannot nodulate S. flavescens, but we obtained 14 Tn5 mutants of B. diazoefficiens that nodulated S. flavescens. This suggested that the mutations had disrupted a negative regulator that prevents nodulation of S. flavescens, leading to nonspecific nodulation. For Ensifer fredii CCBAU 45436 mutants, the minimal NF structure was sufficient for nodulation of soybean and S. flavescens. In summary, the mechanism of promiscuous symbiosis of S. flavescens with rhizobia might be related to its nonspecific recognition of NF structures, and the host specificity of rhizobia may also be controlled by currently unknown nodulation-related genes.