Nitrogen-fixing root nodule symbioses (RNS) occur in two major forms-Actinorhiza and legume-rhizobium symbiosis-which differ in bacterial partner, intracellular infection pattern, and morphogenesis. The phylogenetic restriction of nodulation to eurosid angiosperms indicates a common and recent evolutionary invention, but the molecular steps involved are still obscure. In legumes, at least seven genes-including the symbiosis receptor-kinase gene SYMRK-are essential for the interaction with rhizobia bacteria and for the Arbuscular Mycorrhiza (AM) symbiosis with phosphate-acquiring fungi, which is widespread in occurrence and believed to date back to the earliest land plants. We show that SYMRK is also required for Actinorhiza symbiosis of the cucurbit Datisca glomerata with actinobacteria of the genus Frankia, revealing a common genetic basis for both forms of RNS. We found that SYMRK exists in at least three different structural versions, of which the shorter forms from rice and tomato are sufficient for AM, but not for functional endosymbiosis with bacteria in the legume Lotus japonicus. Our data support the idea that SYMRK sequence evolution was involved in the recruitment of a pre-existing signalling network from AM, paving the way for the evolution of intracellular root symbioses with nitrogen-fixing bacteria.