The CLAVATA3/embryo-surrounding region (CLE) peptides control the fine balance between proliferation and differentiation in plant development. We studied the role of CLE peptides during indeterminate nodule development and identified 25 MtCLE peptide genes in the Medicago truncatula genome, of which two genes, MtCLE12 and MtCLE13, had nodulation-related expression patterns that were linked to proliferation and differentiation. MtCLE13 expression was up-regulated early in nodule development. A high-to-low expression gradient radiated from the inner toward the outer cortical cell layers in a region defining the incipient nodule. At later stages, MtCLE12 and MtCLE13 were expressed in differentiating nodules and in the apical part of mature, elongated nodules. Functional analysis revealed a putative role for MtCLE12 and MtCLE13 in autoregulation of nodulation, a mechanism that controls the number of nodules and involves systemic signals mediated by a leucine-rich repeat receptor-like kinase, SUNN, which is active in the shoot. When MtCLE12 and MtCLE13 were ectopically expressed in transgenic roots, nodulation was abolished at the level of the nodulation factor signal transduction, and this inhibition involved long-distance signaling. In addition, composite plants with roots ectopically expressing MtCLE12 or MtCLE13 had elongated petioles. This systemic effect was not observed in transgenic roots ectopically expressing MtCLE12 and MtCLE13 in a sunn-1 mutant background, although nodulation was still strongly reduced. These results suggest multiple roles for CLE signaling in nodulation.