Salinity is one of the most important abiotic stresses that adversely affects crop growth and productivity. A subtractive suppression hybridization (SSH) library were constructed from the roots of salt-sensitive Yulu cultivar melon seedlings under salt stress; 557 high-quality expressed sequence tags (ESTs) were randomly sequenced, with an average size of 428 bp, which assembled into 68 contigs and 315 singletons. Compared with our previous SSH library generated from the salt-tolerant Bingxuecui cultivar, the proportion of transcripts involved in metabolism, protein fate, cellular communication/signal transduction mechanisms, and cell rescue/defense were 4, 1.46, 0.94, and 0.4% higher, respectively, in the salt-tolerant cultivar than the in salt-sensitive cultivar. Quantitative real-time PCR analysis of eleven transcripts revealed temporal variations in their expression in the two cultivars under salt stress. One NAC gene (JZ477011) was heterologously expressed in yeast for functional characterization, and enhanced the sensitivity of yeast cells to high-salinity to salt stress and inhibited their growth. Information regards to their functions would aid in the understanding of response mechanisms to saline stress and in the development of molecular markers for selecting salt-tolerant melon cultivars.