Macrocycles, including macrocyclic peptides, have shown promise for targeting challenging protein-protein interactions (PPIs). One PPI of high interest is between Kelch-like ECH-Associated Protein-1 (KEAP1) and Nuclear Factor (Erythroid-derived 2)-like 2 (Nrf2). Guided by X-ray crystallography, NMR, modeling, and machine learning, we show that the full 20 nM binding affinity of Nrf2 for KEAP1 can be recapitulated in a cyclic 7-mer peptide, c[(D)-beta-homoAla-DPETGE]. This compound was identified from the Nrf2-derived linear peptide GDEETGE (K-D = 4.3 mu M) solely by optimizing the conformation of the cyclic compound, without changing any KEAP1 interacting residue. X-ray crystal structures were determined for each linear and cyclic peptide variant bound to KEAP1. Despite large variations in affinity, no obvious differences in the conformation of the peptide binding residues or in the interactions they made with KEAP1 were observed. However, analysis of the X-ray structures by machine learning showed that locations of strain in the bound ligand could be identified through patterns of subangstrom distortions from the geometry observed for unstrained linear peptides. We show that optimizing the cyclic peptide affinity was driven partly through conformational preorganization associated with a proline substitution at position 78 and with the geometry of the noninteracting residue Asp77 and partly by decreasing strain in the ETGE motif itself. This approach may have utility in dissecting the trade-off between conformational preorganization and strain in other ligand-receptor systems. We also identify a pair of conserved hydrophobic residues flanking the core DxETGE motif which play a conformational role in facilitating the high-affinity binding of Nrf2 to KEAP1.