Kallikrein-related peptidase 4 (KLK4) is a serine protease that has putative intracellular and extracellular functions in prostate cancer progression. Here we show that MCoTI-II, a 34-amino acid cyclic peptide found in the seeds of red gac (Momordica cochinchinensis), is an inhibitor of KLK4. By grafting a preferred KLK4 cleavage sequence into MCoTI-II, we produced a highly potent KLK4 inhibitor (K i = 0.1 nM) that displayed 100,000-fold selectivity over related KLKs and the ability to penetrate cells. Additionally, by substituting positively charged noncontact residues in this compound, we produced a potent and selective KLK4 inhibitor that does not penetrate cells. The inhibitors were shown to be nontoxic to human cells and stable in human serum. These KLK4 inhibitors provide useful chemical tools to further define the role(s) of both intracellular and extracellular KLK4 in prostate cancer cell lines and disease models.