Most laboratory evolution studies that characterize evolutionary adaptation genomically focus on genetically simple traits that can be altered by one or few mutations. Such traits are important, but they are few compared with complex, polygenic traits influenced by many genes. We know much less about complex traits, and about the changes that occur in the genome and in gene expression during their evolutionary adaptation. Salt stress tolerance is such a trait. It is especially attractive for evolutionary studies, because the physiological response to salt stress is well-characterized on the molecular and transcriptome level. This provides a unique opportunity to compare evolutionary adaptation and physiological adaptation to salt stress. The yeast Saccharomyces cerevisiae is a good model system to study salt stress tolerance, because it contains several highly conserved pathways that mediate the salt stress response. We evolved three replicate lines of yeast under continuous salt (NaCl) stress for 300 generations. All three lines evolved faster growth rate in high salt conditions than their ancestor. In these lines, we studied gene expression changes through microarray analysis and genetic changes through next generation population sequencing. We found two principal kinds of gene expression changes, changes in basal expression (82 genes) and changes in regulation (62 genes). The genes that change their expression involve several well-known physiological stress-response genes, including CTT1, MSN4 and HLR1. Next generation sequencing revealed only one high-frequency single-nucleotide change, in the gene MOT2, that caused increased fitness when introduced into the ancestral strain. Analysis of DNA content per cell revealed ploidy increases in all the three lines. Our observations suggest that evolutionary adaptation of yeast to salt stress is associated with genome size increase and modest expression changes in several genes.