Some plants can fix atmospheric nitrogen by hosting symbiotic diazotrophic rhizobia or Frankia bacteria in root organs, known as nodules. Such nodule symbiosis occurs in ten lineages in four taxonomic orders; Fabales, Fagales, Cucurbitales and Rosales, which collectively are known as the nitrogen-fixing clade (NFC). Based on differences in ontogeny and histology, nodules have been divided into two types: legume-type and actinorhizal-type nodules. The evolutionary relationship between these nodule types has been a long-standing enigma for molecular and evolutionary biologists. Recent phylogenomic studies on nodulating and non-nodulating species in the NFC indicated a shared evolutionary origin of the nodulation trait in all ten lineages. However, this hypothesis faces a conundrum that legume-type and actinorhizal-type nodules have been regarded as fundamentally different. Here, we analysed the actinorhizal-type nodules formed by Parasponia andersonii (Rosales) and Alnus glutinosa (Fagales), and found that their ontogeny is more similar to that of legume-type nodules (Fabales) than generally assumed. We also show that in Medicago truncatula a homeotic mutation in the co-transcriptional regulator encoding gene NODULE ROOT1 (MtNOOT1) converts a legume-type nodule into actinorhizal type. These experimental findings suggest that the two nodule types have a shared evolutionary origin.