Salinity is one of the major abiotic factors affecting alfalfa productivity. Identifying genes that control this complex trait will provide critical insights for alfalfa breeding programs. To date, no studies have been published on a deep sequencing-based profiling of the alfalfa transcriptome in response to salinity stress. Observations gathered through research on reference genomes may not always be applicable to alfalfa. In this work, Illumina RNA-sequencing was performed in two alfalfa genotypes contrasting in salt tolerance, in order to estimate a broad spectrum of genes affected by salt stress. A total of 367,619,586 short reads were generated from cDNA libraries originated from roots of both lines. More than 60,000 tentative consensus sequences (TCs) were obtained and, among them, 74.5% had a significant similarity to proteins in the NCBI database. Mining of simple sequence repeats (SSRs) from all TCs revealed 6,496 SSRs belonging to 3,183 annotated unigenes. Bioinformatics analysis showed that the expression of 1,165 genes, including 86 transcription factors (TFs), was significantly altered under salt stress. About 40% of differentially expressed genes were assigned to known gene ontology (GO) categories using Arabidopsis GO. A random check of differentially expressed genes by quantitative real-time PCR confirmed the bioinformatic analysis of the RNA-seq data. A number of salt-responsive genes in both tested genotypes were identified and assigned to functional classes, and gene candidates with roles in the adaptation to salinity were proposed. Alfalfa-specific data on salt-responsive genes obtained in this work will be useful in understanding the molecular mechanisms of salinity tolerance in alfalfa.