Some plants fix atmospheric nitrogen by hosting symbiotic diazotrophic rhizobia or Frankia bacteria in root organs known as nodules. Such nodule symbiosis occurs in 10 plant lineages in four taxonomic orders: Fabales, Fagales, Cucurbitales, and Rosales, which are collectively known as the nitrogen-fixing clade. Nodules are divided into two types based on differences in ontogeny and histology: 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 nonnodulating species in the nitrogen-fixing clade indicated that the nodulation trait has a shared evolutionary origin in all 10 lineages. However, this hypothesis faces a conundrum in that legume-type and actinorhizal-type nodules have been regarded as fundamentally different. Here, we analyzed 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 gene NODULE ROOT1 (MtNOOT1) converts legume-type nodules into actinorhizal-type nodules. These experimental findings suggest that the two nodule types have a shared evolutionary origin.