To investigate the genetic basis of microbial evolutionary adaptation to salt (NaCl) stress, populations of Desulfovibrio vulgaris Hildenborough (DvH), a sulfate-reducing bacterium important for the biogeochemical cycling of sulfur, carbon and nitrogen, and potentially the bioremediation of toxic heavy metals and radionuclides, were propagated under salt stress or non-stress conditions for 1200 generations. Whole-genome sequencing revealed 11 mutations in salt stress-evolved clone ES9-11 and 14 mutations in non-stress-evolved clone EC3-10. Whole-population sequencing data suggested the rapid selective sweep of the pre-existing polymorphisms under salt stress within the first 100 generations and the slow fixation of new mutations. Population genotyping data demonstrated that the rapid selective sweep of pre-existing polymorphisms was common in salt stress-evolved populations. In contrast, the selection of pre-existing polymorphisms was largely random in EC populations. Consistently, at 100 generations, stress-evolved population ES9 showed improved salt tolerance, namely increased growth rate (2.0-fold), higher biomass yield (1.8-fold) and shorter lag phase (0.7-fold) under higher salinity conditions. The beneficial nature of several mutations was confirmed by site-directed mutagenesis. All four tested mutations contributed to the shortened lag phases under higher salinity condition. In particular, compared with the salt tolerance improvement in ES9-11, a mutation in a histidine kinase protein gene lytS contributed 27% of the growth rate increase and 23% of the biomass yield increase while a mutation in hypothetical gene DVU2472 contributed 24% of the biomass yield increase. Our results suggested that a few beneficial mutations could lead to dramatic improvements in salt tolerance.