For over two decades now, it is known that the nodule symbiosis between legume plants and nitrogen fixing rhizobium bacteria is set in motion by the bacterial signal molecule named nodulation (Nod) factor. Upon Nod factor perception a signaling cascade is activated that is also essential for endomycorrhizal symbiosis (Fig. 1). This suggests that rhizobium co-opted the evolutionary far more ancient mycorrhizal signaling pathway in order to establish an endosymbiotic interaction with legumes. As arbuscular mycorrhizal fungi of the Glomeromycota phylum can establish a symbiosis with the fast majority of land plants, it is most probable that this signaling cascade is wide spread in plant kingdom. However, Nod factor perception generally is considered to be unique to legumes. Two recent breakthroughs on the evolutionary origin of Rhizobium Nod factor signaling demonstrate that this is not the case. The purification of Nod factor-like molecules excreted by the mycorrhizal fungus Glomus intraradices and the role of the LysM-type Nod factor receptor PaNFP in the non-legume Parasponia andersonii provide novel understanding on the evolution of rhizobial Nod factor signaling.