Abstract: Despite recent success in computational design of structured cyclic peptides, de novo design of cyclic peptides that bind to any protein functional site remains difficult. To address this challenge, we developed a computational “anchor extension” methodology for targeting protein interfaces by extending a peptide chain around a non-canonical amino acid residue anchor. To test our approach using a well characterized model system, we design cyclic peptides that inhibit histone deacetylases 2 and 6 (HDAC2 and HDAC6) with enhanced potency compared to the original anchor (IC50 values of 9.1 and 4.4 nM for the best binders compared to 5.4 and 0.6 μM for the anchor, respectively). The HDAC6 inhibitor is among the most potent reported inhibitors so far. These results highlight the potential for de novo design of high-affinity protein-peptide interfaces, as well as the challenges that remain.