Cytokinin regulates many aspects of plant development, and in legume crops, this phytohormone is necessary and sufficient for symbiotic nodule organogenesis, allowing them to fix atmospheric nitrogen. To identify direct links between cytokinins and nodule organogenesis, we determined a consensus sequence bound in vitro by a transcription factor (TF) acting in cytokinin signaling, the nodule-enhanced Medicago truncatula Mt RR1 response regulator (RR). Among genes rapidly regulated by cytokinins and containing this so-called RR binding site (RRBS) in their promoters, we found the nodulation-related Type-A RR Mt RR4 and the Nodulation Signaling Pathway 2 (NSP2) TF. Site-directed mutagenesis revealed that RRBS cis-elements in the RR4 and NSP2 promoters are essential for expression during nodule development and for cytokinin induction. Furthermore, a microRNA targeting NSP2 (miR171 h) is also rapidly induced by cytokinins and then shows an expression pattern anticorrelated with NSP2. Other primary targets regulated by cytokinins depending on the Cytokinin Response1 (CRE1) receptor were a cytokinin oxidase/dehydrogenase (CKX1) and a basic Helix-Loop-Helix TF (bHLH476). RNA interference constructs as well as insertion of a Tnt1 retrotransposon in the bHLH gene led to reduced nodulation. Hence, we identified two TFs, NSP2 and bHLH476, as direct cytokinin targets acting at the convergence of phytohormonal and symbiotic cues.