Infection by Hepatitis C Virus (HCV) leads to a slowly progressing disease that over two decades can lead to liver cirrhosis or liver cancer. Currently, one of the most promising approaches to anti-HCV therapy is the development of inhibitors of the NS3/4A protease, which is essential for maturation of the viral polyprotein. Several substrate-derived inhibitors of NS3/4A have been described, all taking advantage of binding to the S subsite of the enzyme. Inspection of the S' subsite of NS3/4A shows binding pockets which might be exploited for inhibitor binding, but due to the fact that ground-state binding to the S' subsite is not used by the substrate, this does not represent a suitable starting point. We have now optimized S'-binding in the context of noncleavable decapeptides spanning P6-P4'. Binding was sequentially increased by introduction of the previously optimized P-region [Ingallinella et al. (1998) Biochemistry 37, 8906-8914], change of the P4' residue, and combinatorial optimization of positions P2'-P3'. The overall process led to an increase in binding of more than 3 orders of magnitude, with the best decapeptide showing IC(50) < 200 pM. The binding mode of the decapeptides described in the present work shares features with the binding mode of the natural substrates, together with novel interactions within the S' subsite. Therefore, these peptides may represent an entry point for a novel class of NS3 inhibitors.