Proteases are vital for virus proliferation and have been found to play key roles in cancer metastasis. Identifying protease substrates allows determination of their function and can aid in inhibitor design. We recently reported a method of identifying substrates using cellular libraries of peptide substrates (CLiPS). Here we report improvement of this method to increase the sorting efficiency for protease substrates and high-throughput analysis of the individual substrates. We applied this method to tobacco etch virus(TEV) protease, which is widely used in protein purification. By iterative library creation and screening, we found optimum substrates that are similar to the widely reported TEV substrate. This method will aid in rapid identification of protease substrates, enabling better understanding of these proteases and design of inhibitors for therapeutic applications.