We previously designed the consensus signal peptide (CSP) and demonstrated that it can be used to strongly stimulate heterologous protein production in Escherichia coli. A comparative study using CSP and two bacterial signal sequences, pelB and ompA, showed that the effect of signal sequences on both expression level and translocation efficiency can be highly protein specific. We report here the generation of CSP mutant libraries by a combinatorial mutagenesis approach. Degenerated CSP oligonucleotides were cloned in frame with the 5' end of the bla gene, encoding the mature periplasmic β-lactamase released from its native signal sequence. This novel design allows for a direct selection of improved signal sequences that positively affect the expression level and/or translocation efficiency of β-lactamase, based on the ampicillin tolerance level of the E. coli host cells. By using this strategy, 61 different CSP mutants with up to 8-fold-increased ampicillin tolerance level and up to 5.5-fold-increased β-lactamase expression level were isolated and characterized genetically. A subset of the CSP mutants was then tested with the alternative reporter gene phoA, encoding periplasmic alkaline phosphatase (AP), resulting in an up to 8-fold-increased production level of active AP protein in E. coli. Moreover, it was demonstrated that the CSP mutants can improve the production of the medically important human interferon α2b under high-cell-density cultivations. Our results show that there is a clear potential for improving bacterial signal sequences by using combinatorial mutagenesis, and bioinformatics analyses indicated that the beneficial mutations could not be rationally predicted.