Background: Acetic acid, released during hydrolysis of lignocellulosic feedstocks for second generation bioethanol production, inhibits yeast growth and alcoholic fermentation. Yeast biomass generated in a propagation step that precedes ethanol production should therefore express a high and constitutive level of acetic acid tolerance before introduction into lignocellulosic hydrolysates. However, earlier laboratory evolution strategies for increasing acetic acid tolerance of Saccharomyces cerevisiae, based on prolonged cultivation in the presence of acetic acid, selected for inducible rather than constitutive tolerance to this inhibitor. Results: Preadaptation in the presence of acetic acid was shown to strongly increase the fraction of yeast cells that could initiate growth in the presence of this inhibitor. Serial microaerobic batch cultivation, with alternating transfers to fresh medium with and without acetic acid, yielded evolved S. cerevisiae cultures with constitutive acetic acid tolerance. Single-cell lines isolated from five such evolution experiments after 50-55 transfers were selected for further study. An additional constitutively acetic acid tolerant mutant was selected after UV-mutagenesis. All six mutants showed an increased fraction of growing cells upon a transfer from a non-stressed condition to a medium containing acetic acid. Whole-genome sequencing identified six genes that contained (different) mutations in multiple acetic acid-tolerant mutants. Haploid segregation studies and expression of the mutant alleles in the unevolved ancestor strain identified causal mutations for the acquired acetic acid tolerance in four genes (ASG1, ADH3, SKS1 and GIS4). Effects of the mutations in ASG1, ADH3 and SKS1 on acetic acid tolerance were additive. Conclusions: A novel laboratory evolution strategy based on alternating cultivation cycles in the presence and absence of acetic acid conferred a selective advantage to constitutively acetic acid-tolerant mutants and may be applicable for selection of constitutive tolerance to other stressors. Mutations in four genes (ASG1, ADH3, SKS1 and GIS4) were identified as causative for acetic acid tolerance. The laboratory evolution strategy as well as the identified mutations can contribute to improving acetic acid tolerance in industrial yeast strains.