Predicting protein-peptide complex structures is crucial to the understanding of a vast variety of peptide-mediated cellular processes and to peptide-based drug development. Peptide flexibility and binding mode ranking are the two major challenges for protein-peptide complex structure prediction. Peptides are highly flexible molecules, and therefore, brute-force modeling of peptide conformations of interest in protein-peptide docking is beyond current computing power. Inspired by the fact that the protein-peptide binding process is like protein folding, we developed a novel strategy, named MDockPeP2, which tries to address these challenges using physicochemical information embedded in abundant monomeric proteins with an exhaustive search strategy, in combination with an integrated global search and a local flexible minimization method. Only the peptide sequence and the protein crystal structure are required. The method was systemically assessed using a newly constructed structural database of 89 nonredundant protein-peptide complexes with the peptide sequence length ranging from 5 to 29 in which about half of the peptides are longer than 15 residues. MDockPeP2 yielded a total success rate of 58.4% (70.8, 79.8%) for the bound docking (i.e., with the bound receptor and fully flexible peptides) and 19.0% (44.8, 70.7%) for the challenging unbound docking when top 10 (100, 1000) models were considered for each prediction. MDockPeP2 achieved significantly higher success rates on two other datasets, peptiDB and LEADS-PEP, which contain only short- and medium-size peptides (≤ 15 residues). For peptiDB, our method obtained a success rate of 62.0% for the bound docking and 35.9% for the unbound docking when the top 10 models were considered. For LEADS-PEP, MDockPeP2 achieved a success rate of 69.8% when the top 10 models were considered. The program is available at https://zougrouptoolkit.missouri.edu/mdockpep2/download.html.