Hexavalent chromium [Cr(VI)] is a common environmental pollutant. However, little is known about the genetic basis of microbial evolution under Cr(VI) stress and the influence of the prior evolution histories on the subsequent evolution under Cr(VI) stress. In this study, Desulfovibrio vulgaris Hildenborough (DvH), a model sulfate-reducing bacterium, was experimentally evolved for 600 generations. By evolving the replicate populations of three genetically diverse DvH clones, including ancestor (AN, without prior experimental evolution history), non-stress-evolved EC3-10, and salt stress-evolved ES9-11, the contributions of adaptation, chance, and pre-existing genetic divergence to the evolution under Cr(VI) stress were able to be dissected. Significantly decreased lag phases under Cr(VI) stress were observed in most evolved populations, while increased Cr(VI) reduction rates were primarily observed in populations evolved from EC3-10 and ES9-11. The pre-existing genetic divergence in the starting clones showed strong influences on the changes in lag phases, growth rates, and Cr(VI) reduction rates. Additionally, the genomic mutation spectra in populations evolved from different starting clones were significantly different. A total of 14 newly mutated genes obtained mutations in at least two evolved populations, suggesting their importance in Cr(VI) adaptation. An in-frame deletion mutation of one of these genes, the chromate transporter gene DVU0426, demonstrated that it played an important role in Cr(VI) tolerance. Overall, our study identified potential key functional genes for Cr(VI) tolerance and demonstrated the important role of pre-existing genetic divergence in evolution under Cr(VI) stress conditions.