Pairwise comparisons of Genista tinctoria (dyer’s weed) rhizobium nodA, nodC, and nodZ gene sequences to those available in databanks revealed their highest sequence identities to nodulation loci of Bradyrhizobium sp. (Lupinus) strains and rhizobia from other genistoid legumes. On phylogenetic trees, genistoid microsymbionts were grouped together in monophyletic clusters, which suggested that their nodulation genes evolved from a common ancestor. G. tinctoria nodulators formed symbioses not only with the native host, but also with other plants of Genisteae tribe such as: Lupinus luteus, Sarothamnus scoparius, and Chamaecytisus ratisbonensis, and they were classified as the genistoid cross-inoculation group. The dyer’s weed root nodules were designated as indeterminate with apical meristem consisting of infected and uninfected cells.