Legumes host their Rhizobium spp. symbiont in novel root organs called nodules. Nodules originate from differentiated root cortical cells that dedifferentiate and subsequently form nodule primordia, a process controlled by cytokinin. A whole-genome duplication has occurred at the root of the legume Papilionoideae subfamily. We hypothesize that gene pairs originating from this duplication event and are conserved in distinct Papilionoideae lineages have evolved symbiotic functions. A phylogenetic strategy was applied to search for such gene pairs to identify novel regulators of nodulation, using the cytokinin phosphorelay pathway as a test case. In this way, two paralogous type-A cytokinin response regulators were identified that are involved in root nodule symbiosis. Response Regulator9 (MtRR9) and MtRR11 in medicago (Medicago truncatula) and an ortholog in lotus (Lotus japonicus) are rapidly induced upon Rhizobium spp. Nod factor signaling. Constitutive expression of MtRR9 results in arrested primordia that have emerged from cortical, endodermal, and pericycle cells. In legumes, lateral root primordia are not exclusively formed from pericycle cells but also require the involvement of the root cortical cell layer. Therefore, the MtRR9-induced foci of cell divisions show a strong resemblance to lateral root primordia, suggesting an ancestral function of MtRR9 in this process. Together, these findings provide a proof of principle for the applied phylogenetic strategy to identify genes with a symbiotic function in legumes.