KLK-related peptidase 6 (KLK6) is highly up-regulated in several types of cancers, including breast and ovarian cancers, where its increased activity promotes invasion and metastasis. Inhibitors that specifically target KLK6, however, have not yet been reported, possibly because KLK6 shares a high sequence homology and structural similarity with other serine proteases and resists inhibition by many polypeptide inhibitors. Here, we present a combinatorial approach for engineering specific KLK6 inhibitors via flow cytometry based screening. This was achieved using yeast-displayed mutant library of the human amyloid precursor protein inhibitor domain (APPI), an inhibitor of other serine proteases, such as anionic and cationic trypsins. On the basis of this screening, we generated a four mutant APPI variant (APPI-4M) with a KLK6 inhibition constant (Ki) of 160 pM and a turnover time of 10 days. To the best of our knowledge, APPI-4M is the most potent KLK6 inhibitor reported to date, displaying 146-fold improved affinity, up to 560-fold greater specificity, and 13-fold improved proteolytic stability compared with wild-type APPI (APPI-WT). We further demonstrate that APPI-4M acts as a functional inhibitor in a cell-based model of KLK6-dependent breast cancer invasion. Moreover, we have solved the crystal structures of the APPI-WT/KLK6 and APPI-4M/KLK6 complexes, revealing the structural and mechanistic bases for the improved KLK6 binding and proteolytic resistance of APPI-4M. Finally, we have used the fact that KLK6 is over-expressed in human ovarian cancer cells, and our latest in vivo results demonstrate the ability of fluorescently-labeled APPI-4M to act as a first-in-class imaging agent for detecting ovarian cancer primary tumors, secondary tumors and more importantly, small metastatic sites. We anticipate that APPI-4M will have substantial translational potential as both an imaging and therapeutic agent.