The establishment of the Legume-Rhizobia symbiosis is generally dependent on the production of rhizobial lipochitooligosaccharidic Nod factors (NFs) and their perception by plant Lysin Motif Receptor-Like Kinases (LysM-RLKs). In this study, we characterized a cluster of LysM-RLK genes implicated in strain-specific recognition in two highly divergent and widely-studied Medicago truncatula genotypes, A17 and R108. We then used reverse genetic approaches and biochemical analyses to study the function of selected genes in the clusters and the ability of their encoded proteins to bind NFs. Our study has revealed that the LYK cluster exhibits a high degree of variability among M. truncatula genotypes, which in A17 and R108 includes recent recombination events within the cluster and a transposon insertion in A17. The essential role of LYK3 in nodulation in A17 is not conserved in R108 despite similar sequences and good nodulation expression profiles. Although, LYK2, LYK5 and LYK5bis are not essential for nodulation of the two genotypes, some evidence points to accessory roles in nodulation, but not through high-affinity NF binding. This work shows that recent evolution in the LYK cluster provides a source of variation for nodulation, and potential robustness of signaling through genetic redundancy.