The root nodule symbiosis of plants with nitrogen-fixing bacteria impacts global nitrogen cycles and food production but is restricted to a subset of genera within a single clade of flowering plants. To explore the genetic basis for this scattered occurrence, we sequenced the genomes of ten plant species covering the diversity of nodule morphotypes, bacterial symbionts and infection strategies. In a genome-wide comparative analysis of a total of 37 plant species, we discovered signatures of multiple independent loss-of-function events in the indispensable symbiotic regulator NODULE INCEPTION (NIN) in ten out of 13 genomes of non-nodulating species within this clade. The discovery that multiple independent losses shaped the present day distribution of nitrogen-fixing root nodule symbiosis in plants reveals a phylogenetically wider distribution in evolutionary history and a so far underestimated selection pressure against this symbiosis.