Due to their ability to catalytically cleave proteins and peptides, proteases present unique opportunities for the use in industrial, biotechnological, and therapeutic applications. The possibility to engineer proteases with redesigned substrate specificities has the potential to expand the scope of practical applications of this enzyme class. We here apply a combinatorial protease engineering 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 of seven positions from the TEV consensus substrate sequence and exhibits high sequence similarity to the aggregation-inducing hydrophobic core region of the amyloid beta (Aβ) peptide. Flow cytometric sorting of a semi-rational TEV protease library led to the enrichment of a set of protease variants that recognize and cleave the novel target substrate.