Rhizobium nitrogen-fixing nodule symbiosis occurs in two taxonomic lineages: legumes (Fabaceae) and the genus Parasponia (Cannabaceae). Both symbioses are initiated upon the perception of rhizobium-secreted lipochitooligosaccharides (LCOs), called Nod factors. Studies in the model legumes Lotus japonicus and Medicago truncatula showed that rhizobium LCOs are perceived by a heteromeric receptor complex of distinct Lys motif (LysM)-type transmembrane receptors named NOD FACTOR RECEPTOR1 (LjNFR1) and LjNFR5 (L. japonicus) and LYSM DOMAIN CONTAINING RECEPTOR KINASE3 (MtLYK3)-NOD FACTOR PERCEPTION (MtNFP; M. truncatula). Recent phylogenomic comparative analyses indicated that the nodulation traits of legumes, Parasponia spp., as well as so-called actinorhizal plants that establish a symbiosis with diazotrophic Frankia spp. bacteria share an evolutionary origin about 110 million years ago. However, the evolutionary trajectory of LysM-type LCO receptors remains elusive. By conducting phylogenetic analysis, transcomplementation studies, and CRISPR-Cas9 mutagenesis in Parasponia andersonii, we obtained insight into the origin of LCO receptors essential for nodulation. We identified four LysM-type receptors controlling nodulation in P. andersonii: PanLYK1, PanLYK3, PanNFP1, and PanNFP2. These genes evolved from ancient duplication events predating and coinciding with the origin of nodulation. Phylogenetic and functional analyses associated the occurrence of a functional NFP2-orthologous receptor to LCO-driven nodulation. Legumes and Parasponia spp. use orthologous LysM-type receptors to perceive rhizobium LCOs, suggesting a shared evolutionary origin of LCO-driven nodulation. Furthermore, we found that both PanLYK1 and PanLYK3 are essential for intracellular arbuscule formation of mutualistic endomycorrhizal fungi. PanLYK3 also acts as a chitin oligomer receptor essential for innate immune signaling, demonstrating functional analogy to CHITIN ELECITOR RECEPTOR KINASE-type receptors.