Fermentation-based bioprocesses rely extensively on strain improvement for commercialization. Whole-cell biocatalysts are commonly limited by low tolerance of extreme process conditions such as temperature, pH, and solute concentration. Rational approaches to improving such complex phenotypes lack good models and are especially difficult to implement without genetic tools. Here we describe the use of genome shuffling to improve the acid tolerance of a poorly characterized industrial strain of Lactobacillus. We used classical strain-improvement methods to generate populations with subtle improvements in pH tolerance, and then shuffled these populations by recursive pool-wise protoplast fusion. We identified new shuffled lactobacilli that grow at substantially lower pH than does the wild-type strain on both liquid and solid media. In addition, we identified shuffled strains that produced threefold more lactic acid than the wild type at pH 4.0. Genome shuffling seems broadly useful for the rapid evolution of tolerance and other complex phenotypes in industrial microorganisms.