The publication of the genome sequence of barrel medic (Medicago truncatula) opens the way to comparative genomic analyses addressing the evolutionary diversification of the core components of plant root endosymbiosis. Our phylogenetic and gene family evolution analyses suggest the independent emergence of genes essential for the establishment of the rhizobium-legume symbiosis from ancestral functions. Most of these "innovatory" genes have homologs in the nonlegume dicot Arabidopsis thaliana and may therefore represent evolutionary adaptations rather than novelties strictly limited to the Rhizobiales-legumes association. By contrast, members of one essential symbiosis gene family were identified uniquely in core eudicots and legumes involved in rhizobial interactions, pointing to their coevolution within these lineages. Our analyses uncover the role of a genomic "toolkit" containing both newly recruited and long-standing gene components of plant endosymbiosis, which sheds new light on the evolutionary and genetic bases of legume adaptation to rhizosphere conditions.