Molecular docking programs play an important role in drug development and many well-established methods exist. However, there are two situations for which the performance of most approaches is still not satisfactory, namely inclusion of receptor flexibility and docking of large, flexible ligands like peptides. In this publication a new approach is presented for docking peptides into flexible receptors. For this purpose a two step procedure was developed: first, the protein-peptide conformational space is scanned and approximate ligand poses are identified and second, the identified ligand poses are refined by a new molecular dynamics-based method, optimized potential molecular dynamics (OPMD). The OPMD approach uses soft-core potentials for the protein-peptide interactions and applies a new optimization scheme to the soft-core potential. Comparison with refinement results obtained by conventional molecular dynamics and a soft-core scaling approach shows significant improvements in the sampling capability for the OPMD method. Thus, the number of starting poses needed for successful refinement is much lower than for the other methods. The algorithm was evaluated on 15 protein-peptide complexes with 2-16mer peptides. Docking poses with peptide RMSD values <2.10 Å from the equilibrated experimental structures were obtained in all cases. For four systems docking into the unbound receptor structures was performed, leading to peptide RMSD values <2.12 Å. Using a specifically fitted scoring function in 11 of 15 cases the best scoring poses featured a peptide RMSD 2.10 Å.