Due to their ability to catalytically cleave proteins and peptides, proteases present unique opportunities for the use in industrial, biotechnological, and therapeutic applications. Engineered proteases with redesigned substrate specificities have the potential to expand the scope of practical applications of this enzyme class. We here apply a combinatorial protease engineering-based screening method that links proteolytic activity to the solubility and correct folding of a fluorescent reporter protein to redesign the substrate specificity of tobacco etch virus (TEV) protease. The target substrate EKLVFQA differs at three out of seven positions from the TEV consensus substrate sequence. Flow cytometric sorting of a semi-rational TEV protease library, consisting of focused mutations of the substrate binding pockets as well as random mutations throughout the enzyme, led to the enrichment of a set of protease variants that recognize and cleave the novel target substrate.