An important objective of computational protein design is the generation of high affinity peptide inhibitors of protein-peptide interactions, both as a precursor to the development of therapeutics aimed at disrupting disease causing complexes, and as a tool to aid investigators in understanding the role of specific complexes in the cell. We have developed a computational approach to increase the affinity of a protein-peptide complex by designing N or C-terminal extensions which interact with the protein outside the canonical peptide binding pocket. In a first in silico test, we show that by simultaneously optimizing the sequence and structure of three to nine residue peptide extensions starting from short (1-6 residue) peptide stubs in the binding pocket of a peptide binding protein, the approach can recover both the conformations and the sequences of known binding peptides. Comparison with phage display and other experimental data suggests that the peptide extension approach recapitulates naturally occurring peptide binding specificity better than fixed backbone design, and that it should be useful for predicting peptide binding specificities from crystal structures. We then experimentally test the approach by designing extensions for p53 and dystroglycan-based peptides predicted to bind with increased affinity to the Mdm2 oncoprotein and to dystrophin, respectively. The measured increases in affinity are modest, revealing some limitations of the method. Based on these in silico and experimental results, we discuss future applications of the approach to the prediction and design of protein-peptide interactions.