Protein expression in Escherichia coli represents the most facile approach for the preparation of non-glycosylated proteins for analytical and preparative purposes. So far, the optimization of recombinant expression has largely remained a matter of trial and error and has relied upon varying parameters, such as expression vector, media composition, growth temperature and chaperone co-expression. Recently several new approaches for the genome-scale engineering of E. coli to enhance recombinant protein expression have been developed. These methodologies now enable the generation of optimized E. coli expression strains in a manner analogous to metabolic engineering for the synthesis of low-molecular-weight compounds. In this review, we provide an overview of strain engineering approaches useful for enhancing the expression of hard-to-produce proteins, including heterologous membrane proteins.