Lactococcus lactis is essential for most cheese making, and this mesophilic bacterium has its growth optimum around 30 °C. We have, through adaptive evolution, isolated a mutant TM29 that grows well up to 39 °C, and continuous growth at 40 °C is possible if pre-incubated at a slightly lower temperature. At the maximal permissive temperature for the wild-type, 38 °C, TM29 grows 33% faster and has a 12% higher specific lactate production rate than its parent MG1363, which results in fast lactate accumulation. Genome sequencing was used to reveal the mutations accumulated, most of which were shown to affect thermal tolerance. Of the mutations with more pronounced effects, two affected expression of single proteins (chaperone; riboflavin transporter), two had pleiotropic effects (RNA polymerase) which changed the gene expression profile, and one resulted in a change in the coding sequence of CDP-diglyceride synthase. A large deletion containing 10 genes was also found to affect thermal tolerance significantly. With this study we demonstrate a simple approach to obtain non-GMO derivatives of the important L. lactis that possess properties desirable by the industry, e.g. thermal robustness and increased rate of acidification. The mutations we have identified provide a genetic basis for further investigation of thermal tolerance.