The rhizobia-legume symbiosis is highly specific. Major host specificity determinants are the bacterial Nod factor signals that trigger the nodulation programme in a compatible host. Nod factors are lipo-chitooligosaccharides (LCOs) varying in the oligosaccharide chain length, the nature of the fatty acids and substitutions on the oligosaccharide. The nod genotype of rhizobia, which forms the genetic basis for this structural variety, includes a set of nodulation genes encoding the enzymes that synthesize LCOs. Allelic and non-allelic variation in these genes ensures the synthesis of different LCO structures by the different rhizobia. The nod genotypes co-evolved with host plant divergence in contrast to the rhizobia, which followed a different evolution. Horizontal gene transfer probably played an important role during evolution of symbiosis. The nod genotypes are particularly well equipped for horizontal gene transfer because of their location on transmissible plasmids and/or on 'symbiosis islands', which are symbiotic regions associated with movable elements.