Melanoma inhibitor of apoptosis (ML-IAP) is a potent anti-apoptotic protein that is upregulated in a number of melanoma cell lines but not expressed in most normal adult tissues. Overexpression of IAP proteins, such as ML-IAP or the ubiquitously expressed X-chromosome-linked IAP (XIAP), in human cancers has been shown to suppress apoptosis induced by a variety of stimuli. Peptides based on the processed N-terminus of Smac/DIABLO can negate the ability of overexpressed ML-IAP or XIAP to suppress drug-induced apoptosis. Such peptides have been demonstrated to bind to the single baculovirus IAP repeat (BIR) of ML-IAP and the third BIR of XIAP with similar high affinities (∼0.5 μM). Herein, we use phage-display of naive peptide libraries and synthetic peptides to investigate the peptide-binding properties of ML-IAP-BIR and XIAP-BIR3. X-ray crystal structures of ML-IAP-BIR in complex with Smac- and phage-derived peptides, together with peptide structure- activity-relationship data, indicate that the peptides can be modified to provide increased binding affinity and selectivity for ML-IAP-BIR relative to XIAP-BIR3. For instance, substitution of Pro3′ in the Smac-based peptide (AVPIAQKSE) with (2S,3S)-3-methylpyrrolidine-2-carboxylic acid [(3S)-methyl-proline] results in a peptide with 7-fold greater affinity for ML-IAP-BIR and about 100-fold specificity for ML-IAP-BIR relative to XIAP-BIR3.