Nod factors are key bacterial signaling molecules regulating the symbiotic interaction between bacteria known as rhizobia and leguminous plants. Studying plant host genes whose expression is affected by Nod factors has given insights into early symbiotic signaling and development. Here, we used a double supernodulating mutant line that shows increased sensitivity to Nod factors to study the Nod factor-regulated transcriptome. Using microarrays containing more than 16,000 70-mer oligonucleotide probes, we identified 643 Nod-factor-regulated genes, including 225 new Nod-factor-upregulated genes encoding many potential regulators. Among the genes found to be Nod factor upregulated, we identified and characterized MtRALFL1 and MtDVL1, which code for two small putative peptide regulators of 135 and 53 amino acids, respectively. Expression analysis confirmed that these genes are upregulated during initial phases of nodulation. Overexpression of MtRALFL1 and MtDVL1 in Medicago truncatula roots resulted in a marked reduction in the number of nodules formed and in a strong increase in the number of aborted infection threads. In addition, abnormal nodule development was observed when MtRALFL1 was overexpressed. This work provides evidence for the involvement of new putative small-peptide regulators during nodulation.