Plant growth and productivity are affected by various abiotic stresses such as heat, drought, cold, salinity, etc. The mechanism of salt tolerance is one of the most important subjects in plant science as salt stress decreases worldwide agricultural production. In our present study we used cDNA-AFLP technique to compare gene expression profiles of a salt tolerant and a salt-sensitive cultivar of foxtail millet (Seteria italica) in response to salt stress to identify early responsive differentially expressed transcripts accumulated upon salt stress and validate the obtained result through quantitative real-time PCR (qRT-PCR). The expression profile was compared between a salt tolerant (Prasad) and susceptible variety (Lepakshi) of foxtail millet in both control condition (L0 and P0) and after 1 h (L1 and P1) of salt stress. We identified 90 transcript-derived fragments (TDFs) that are differentially expressed, out of which 86 TDFs were classified on the basis of their either complete presence or absence (qualitative variants) and 4 on differential expression pattern levels (quantitative variants) in the two varieties. Finally, we identified 27 non-redundant differentially expressed cDNAs that are unique to salt tolerant variety which represent different groups of genes involved in metabolism, cellular transport, cell signaling, transcriptional regulation, mRNA splicing, seed development and storage, etc. The expression patterns of seven out of nine such genes showed a significant increase of differential expression in tolerant variety after 1 h of salt stress in comparison to salt-sensitive variety as analyzed by qRT-PCR. The direct and indirect relationship of identified TDFs with salinity tolerance mechanism is discussed.