CLE peptides are involved in the balance between cell division and differentiation throughout plant development, including nodulation. Previously, two CLE genes of Medicago truncatula, MtCLE12 and MtCLE13, had been identified whose expression correlated with nodule primordium formation and meristem establishment. Gain-of-function analysis indicated that both MtCLE12 and MtCLE13 interact with the SUPER NUMERIC NODULES (SUNN)-dependent auto-regulation of nodulation to control nodule numbers. Here we demonstrate that cytokinin, which is essential for nodule organ formation, regulates MtCLE13 expression. In addition, simultaneous knockdown of MtCLE12 and MtCLE13 resulted in an increase in nodule number, implying that both genes play a role in controlling nodule number. Additionally, a weak link may exist with the ethylene-dependent mechanism that locally controls nodule number.