High salinity is one of the most serious threats to crop production. To understand the molecular basis of plant responses to salt stress better, suppression subtractive hybridization (SSH) and microarray approaches were combined to identify the potential important or novel genes involved in the early stage of tomato responses to severe salt stress. First, SSH libraries were constructed for the root tissue of two cultivated tomato (Solanum lycopersicum) genotypes: LA2711, a salt-tolerant cultivar, and ZS-5, a salt-sensitive cultivar, to compare salt treatment and non-treatment plants. Then a subset of clones from these SSH libraries were used to construct a tomato cDNA array and microarray analysis was carried out to verify the expression changes of this set of clones upon a high concentration of salt treatment at various time points compared to the corresponding non-treatment controls. A total of 201 non-redundant genes that were differentially expressed upon 30 min of severe salt stress either in LA2711 or ZS-5 were identified from microarray analysis; most of these genes have not previously been reported to be associated with salt stress. The diversity of the putative functions of these genes indicated that salt stress resulted in a complex response in tomato plants.