The number of legume root nodules resulting from a symbiosis with rhizobia is tightly controlled by the plant. Certain members of the CLAVATA3/Embryo Surrounding Region (CLE) peptide family, specifically MtCLE12 and MtCLE13 in Medicago truncatula, act in the systemic autoregulation of nodulation (AON) pathway that negatively regulates the number of nodules. Little is known about the molecular pathways that operate downstream of the AON-related CLE peptides. Here, by means of a transcriptome analysis, we show that roots ectopically expressing MtCLE13 deregulate only a limited number of genes, including three down-regulated genes encoding lysin motif receptor-like kinases (LysM-RLKs), among which are the nodulation factor (NF) receptor NF Perception gene (NFP) and two up-regulated genes, MtTML1 and MtTML2, encoding Too Much Love (TML)-related Kelch-repeat containing F-box proteins. The observed deregulation was specific for the ectopic expression of nodulation-related MtCLE genes and depended on the Super Numeric Nodules (SUNN) AON RLK. Moreover, overexpression and silencing of these two MtTML genes demonstrated that they play a role in the negative regulation of nodule numbers. Hence, the identified MtTML genes are the functional counterpart of the Lotus japonicus TML gene shown to be central in the AON pathway. Additionally, we propose that the down-regulation of a subset of LysM-RLK-encoding genes, among which is NFP, might contribute to the restriction of further nodulation once the first nodules have been formed.