Rhizobium nitrogen-fixing nodules are a well-known trait of legumes, but nodules also occur in other plant lineages either with rhizobium or the actinomycete Frankia as microsymbiont. The widely accepted hypothesis is that nodulation evolved independently multiple times, with only a few losses. However, insight in the evolutionary trajectory of nodulation is lacking. We conducted comparative studies using Parasponia (Cannabaceae), the only non-legume able to establish nitrogen fixing nodules with rhizobium. This revealed that Parasponia and legumes utilize a large set of orthologous symbiosis genes. Comparing genomes of Parasponia and its non-nodulating relative Trema did not reveal specific gene duplications that could explain a recent gain of nodulation in Parasponia. Rather, Trema and other non-nodulating species in the order Rosales show evidence of pseudogenization or loss of key symbiosis genes. This demonstrates that these species have lost the potential to nodulate. This finding challenges a long-standing hypothesis on evolution of nitrogen-fixing symbioses, and has profound implications for translational approaches aimed at engineering nitrogen-fixing nodules in crop plants.