Vitamin K2 is an important vitamin for human health. Vitamin K2 enrichment in the human diet is possible by using vitamin K2-producing bacteria such as Lactococcus lactis in food fermentations. Based on previous observations that aerated cultivation conditions improved vitamin K2 content in L. lactis, we performed laboratory evolution on L. lactis MG1363 by cultivating this strain in a shake flask in a sequential propagation regime with transfers to a fresh medium every 72h. After 100 generations of propagation, we selected three evolved strains that showed improved stationary phase survival in oxygenated conditions. In comparison to the original strain MG1363, the evolved strains showed 50–110% increased vitamin K2 content and exhibited high resistance against hydrogen peroxide-induced oxidative stress. Genome sequencing of the evolved strains revealed common mutations in the genes ldh and gapB. Proteomics analysis revealed overproduction of glyceraldehyde 3-phosphate dehydrogenase (GapA), universal stress protein A2 (UspA2), and formamidopyrimidine-DNA glycosylase (MutM) under aerated conditions in evolved strains, proteins with putative functions in redox reactions, universal stress response, and DNA damage repair, all of which could contribute to the enhanced oxidative stress resistance. The mechanisms underlying elevated vitamin K2 content in the evolved strains remain to be elucidated. Two out of the three evolved strains performed similar to the original strain MG1363 in terms of growth and acidification of culture media. In conclusion, this study demonstrated a natural selection approach without genetic manipulations to obtain vitamin K2 overproducers that are highly relevant for food applications and contributed to the understanding of oxidative stress resistance in L. lactis.