Nitrogen-fixing root nodule symbiosis can sustain the development of the host plants under nitrogen-limiting conditions. Such symbiosis occurs only in a clade of angiosperms known as the nitrogen-fixing clade (NFC). It has long been proposed that root nodule symbiosis evolved several times (in parallel) in the NFC. Two recent phylogenomic studies compared the genomes of nodulating and related non-nodulating species across the four orders of the NFC and found that genes essential for nodule formation are lost or pseudogenized in the non-nodulating species. As these symbiosis genes are specifically involved in the symbiotic interaction, it means that the presence of pseudogenes and the loss of symbiosis genes strongly suggest that their ancestor, which still had functional genes, most likely had a symbiosis with nitrogen-fixing bacteria. These findings agree with the hypothesis that nodulation evolved once at the common ancestor of the NFC, and challenge the hypothesis of parallel evolution. In this chapter, we will cover the current understandings on actinorhizal-type and legume nodule development, and discuss the evolution of the legume nodule type.