Engineering improved protease activity using directed evolution is challenged by uncertainty in sequence-function mapping and inefficiency in evaluating activity of candidate mutants. We implemented a generalizable yeast surface display approach that co-displays protease mutants with substrate on the same Aga2 anchor protein. Identification of enhanced activity mutants is enabled by protease cleavage of tethered substrate removing an N-terminal epitope tag, which empowers flow cytometric isolation of cells with a decrease in signal from fluorophore-linked anti-epitope antibodies. The sequence space of tobacco etch virus protease (TEVp), commonly used for specific cleavage of recombinant protein affinity tags, has previously been investigated through random mutagenesis. Leveraging our display platform, we performed high throughput screens on seven active site combinatorial libraries created via saturation mutagenesis. Beneficial mutations were incorporated into a single second-generation library, which was screened to identify individual beneficial mutations that performed optimally in a multi-mutant context. The vast majority of resultant TEVp multi-mutants improved catalytic efficiency, generally by decreasing KM. The yeast surface protease/substrate co-display system, the insights gleaned on rational library design and mutation combination strategy, and the TEVp sequence-function map will aid future protease engineering efforts.