The number of protein-peptide interactions in a cell is so large that experimental determination of all these complex structures would be a daunting task. Although homology modeling and refinement protocols have vastly improved the number and quality of predicted structural models, ab initio methods are still challenged by both the large number of possible docking sites and the conformational space accessible to flexible peptides. We present a method that addresses these challenges by sampling the entire accessible surface of a protein with a reduced conformational space of interacting backbone fragment pairs from unrelated structures. We demonstrate its potential by predicting ab initio the bound structure for a variety of protein-peptide complexes. In addition, we show the potential of our method for the discovery of domain interaction sites and domain-domain docking.