The bio-based production of added-value compounds (with applications as pharmaceuticals, biofuels, food ingredients, and building blocks) using bacterial platforms is a well-established industrial activity. The design and construction of microbial cell factories (MCFs) with robust and stable industrially relevant phenotypes, however, remains one of the biggest challenges of contemporary biotechnology. In this review, traditional and cutting-edge approaches for optimizing the performance of MCFs for industrial bioprocesses, rooted on the engineering principle of natural evolution (i.e., genetic variation and selection), are discussed. State-of-the-art techniques to manipulate and increase genetic variation in bacterial populations and to construct combinatorial libraries of strains, both globally (i.e., genome level) and locally (i.e., individual genes or pathways, and entire sections and gene clusters of the bacterial genome) are presented. Cutting-edge screening and selection technologies applied to isolate MCFs displaying enhanced phenotypes are likewise discussed. The review article is closed by presenting future trends in the design and construction of a new generation of MCFs that will contribute to the long-sought-after transformation from a petrochemical industry to a veritable sustainable bio-based industry.