CLE (CLAVATA3/ENDOSPERM SURROUNDING REGION-related) peptides are systemic regulators of legume-rhizobium symbiosis that negatively control the number of nitrogen-fixing nodules. In Medicago truncatula, the expression of the MtCLE35 gene is activated in response to rhizobial inoculation and nitrate treatment, and its overexpression systemically inhibits nodulation. However, little is known about the molecular mechanisms underlying MtCLE35-mediated inhibition of nodulation. In order to elucidate target genes regulated by the MtCLE35-induced signaling cascade, we analyzed the transcriptome of MtCLE35-overexpressing roots inoculated by rhizobia using MACE (Massive Analysis of cDNA Ends) sequencing. Totally, 1390 genes were found to be differentially expressed between MtCLE35-overexpressing (35S::MtCLE35) and control (35S::GUS) roots after rhizobial inoculation, among them 268 genes were upregulated and 1122 genes were downregulated. Among downregulated genes, many known regulators of legume-rhizobia symbiosis were found. Genes upregulated in rhizobia-inoculated MtCLE35-overexpressing roots included ones associated with defense response and cellular redox status. Furthermore, stable transgenic plants overexpressing the MtCLE35 gene were obtained in this study, and gene expression qPCR analysis of selected differentially expressed genes in rhizobia-inoculated roots was performed in such plants. Collectively, our data suggest that overexpression of the MtCLE35 gene prevents the induction of nodulation program, which is accompanied by the expression of defense-related gene in MtCLE35-overexpressing rhizobia-inoculated M. truncatula roots.