Microbial starter cultures are essential for consistent product quality and functional properties such as flavor, texture, pH or the alcohol content of various fermented foods. Strain improvement programs to achieve desired properties in starter cultures are diverse, but developments in next-generation sequencing lead to an increased interest in evolutionary engineering of desired phenotypes. We here discuss recent developments of strain selection protocols and how computational approaches can assist such experimental design. Furthermore the analysis of evolved phenotypes and possibilities with complex consortia are highlighted. Studies carried out with mainly yeast and lactic acid bacteria demonstrate the power of evolutionary engineering to deliver strains with novel phenotypes as well as insight into underlying mechanisms.