Leguminous plants establish a symbiosis with rhizobia to enable nitrogen fixation in root nodules under the control of the presumed root-to-shoot-to-root negative feedback called autoregulation of nodulation. In Lotus japonicus, autoregulation is mediated by CLE-RS genes that are specifically expressed in the root, and the receptor kinase HAR1 that functions in the shoot. However, the mature functional structures of CLE-RS gene products and the molecular nature of CLE-RS/HAR1 signalling governed by these spatially distant components remain elusive. Here we show that CLE-RS2 is a post-translationally arabinosylated glycopeptide derived from the CLE domain. Chemically synthesized CLE-RS glycopeptides cause significant suppression of nodulation and directly bind to HAR1 in an arabinose-chain and sequence-dependent manner. In addition, CLE-RS2 glycopeptide specifically produced in the root is found in xylem sap collected from the shoot. We propose that CLE-RS glycopeptides are the long sought mobile signals responsible for the initial step of autoregulation of nodulation.