Docking algorithms play an important role in the process of rational drug design and in understanding the mechanism of molecular recognition. An important determinant for successful docking is the extent to which the configurational space (including conformational changes) of the ligand/receptor system is searched. Here we describe a new, combinatorial method for flexible docking of peptides to proteins that allows full rotation around all single bonds of the peptide ligand and around those of a large set of receptor side chains. We have simulated the binding of several viral peptides to murine major histocompatibility complex class I H-2Kb. In addition, we have explored the limits of our method by simulating a complex between calmodulin and an 18-residue long helical peptide from calmodulin-dependent protein kinase IIalpha. The calculated peptide conformations generally matched well with the X-ray structures. Essential information about local flexibility and about residues that are responsible for strong binding was obtained. We have frequently observed considerable side-chain flexibility during the simulations, showing the need for a flexible treatment of the receptor. Our method may also be useful whenever the receptor side-chain conformation is not available or uncertain, as illustrated by the docking of an H-2Kb binding nonapeptide to the receptor structure taken from an octapeptide/H-2Kb complex.