We set up a large-scale suppression subtractive hybridization (SSH) approach to identify Medicago truncatula genes differentially expressed at different stages of the symbiotic interaction with Sinorhizobium meliloti, with a particular interest for regulatory genes. We constructed 7 SSH libraries covering successive stages from Nod factor signal transduction to S. meliloti infection, nodule organogenesis, and functioning. Over 26,000 clones were differentially screened by two rounds of macroarray hybridizations. In all, 3,340 clones, corresponding to genes whose expression was potentially affected, were selected, sequenced, and ordered into 2,107 tentative gene clusters, including 767 MtS clusters corresponding to new M. truncatula genes. In total, 52 genes encoding potential regulatory proteins, including transcription factors (TFs) and other elements of signal transduction cascades, were identified. The expression pattern of some of them was analyzed by quantitative reverse-transcription polymerase chain reaction in wild-type and in Nod¯ M. truncatula mutants blocked before or after S. meliloti infection. Three genes, coding for TFs of the bHLH and WRKY families and a C2H2 zinc-finger protein, respectively, were found to be upregulated, following S. meliloti inoculation, in the infection-defective mutant lin, whereas the bHLH gene also was expressed in the root-hair-curling mutant hcl. The potential role of these genes in early symbiotic steps is discussed.