Legume-Rhizobium symbiosis is an example of selective cell recognition controlled by host/non-host determinants. Individual bacterial strains have a distinct host range enabling nodulation of a limited set of legume species and vice versa. We show here that expression of Lotus japonicus Nfr1 and Nfr5 Nod-factor receptor genes in Medicago truncatula and L. filicaulis, extends their host range to include bacterial strains, Mesorhizobium loti or DZL, normally infecting L. japonicus. As a result, the symbiotic program is induced, nodules develop and infection threads are formed. Using L. japonicus mutants and domain swaps between L. japonicus and L. filicaulis NFR1 and NFR5, we further demonstrate that LysM domains of the NFR1 and NFR5 receptors mediate perception of the bacterial Nod-factor signal and that recognition depends on the structure of the lipochitin-oligosaccharide Nod-factor. We show that a single amino-acid variation in the LysM2 domain of NFR5 changes recognition of the Nod-factor synthesized by the DZL strain and suggests a possible binding site for bacterial lipochitin-oligosaccharide signal molecules.