Escherichia coli has been widely used for the production of recombinant proteins. To improve protein production yields in E. coli, directed engineering approaches have been commonly used. However, there are only few reported examples of the isolation of E. coli protein production strains using evolutionary approaches. Here, we first give an introduction to bacterial evolution and mutagenesis to set the stage for discussing how so far selection- and screening-based approaches have been used to isolate E. coli protein production strains. Finally, we discuss how evolutionary approaches may be used in the future to isolate E. coli strains with improved protein production characteristics.