Abstract Background Among semi-aquatic species of the legume genus Aeschynomene, some have the property of being nodulated by photosynthetic Bradyrhizobium lacking the nodABC genes necessary for the synthesis of Nod factors. Knowledge of the specificities underlying this Nod-independent symbiosis has been gained from the model legume Aeschynomene evenia but our understanding remains limited due to the lack of comparative genetics with related taxa using a Nod factor-dependent process. To fill this gap, we combined different approaches to perform a thorough comparative analysis in the genus Aeschynomene. Results This study significantly broadened previous taxon sampling, including in allied genera, in order to construct a comprehensive phylogeny. In the phylogenetic tree, five main lineages were delineated, including a novel lineage, the Nod-independent clade and another one containing a polytomy that comprised several Aeschynomene groups and all the allied genera. This phylogeny was matched with data on chromosome number, genome size and low-copy nuclear gene sequences to reveal the diploid species and a polytomy containing mostly polyploid taxa. For these taxa, a single allopolyploid origin was inferred and the putative parental lineages were identified. Finally, nodulation tests with different Bradyrhizobium strains revealed new nodulation behaviours and the diploid species outside of the Nod-independent clade were compared for their experimental tractability and genetic diversity. Conclusions The extended knowledge of the genetics and biology of the different lineages sheds new light of the evolutionary history of the genus Aeschynomene and they provide a solid framework to exploit efficiently the diversity encountered in Aeschynomene legumes. Notably, our backbone tree contains all the species that are diploid and it clarifies the genetic relationships between the Nod-independent clade and the Nod-dependent lineages. This study enabled the identification of A. americana and A. patula as the most suitable species to undertake a comparative genetic study of the Nod-independent and Nod-dependent symbioses.