Alpha helices form a critical part of the binding interface for many protein-protein interactions, and chemically stabilized synthetic helical peptides can be effective inhibitors of such helix-mediated complexes. In particular, hydrocarbon stapling of peptides to generate constrained helices can improve binding affinity and other peptide properties, but determining the best stapled peptide variant often requires laborious trial and error. Here, we describe the rapid discovery and optimization of a stapled-helix peptide that binds to Mcl-1, an antiapoptotic protein that is overexpressed in many chemoresistant cancers. To accelerate discovery, we developed a peptide library synthesis and screening scheme capable of identifying subtle affinity differences among Mcl-1-binding stapled peptides. We used our method to sample combinations of non-natural amino-acid substitutions that we introduced into Mcl-1 inhibitors in the context of a fixed helix-stabilizing hydrocarbon staple that increased peptide helical content and reduced proteolysis. Peptides discovered in our screen contained surprising substitutions at sites that are conserved in natural binding partners. Library-identified peptide M3d is the most potent molecule yet tested for selectively triggering mitochondrial permeabilization in Mcl-1 dependent cell lines. Our library approach for optimizing helical peptide inhibitors can be readily applied to the study of other biomedically important targets.