Inspired by the current representation of the ligand-receptor binding process, a normal-mode-based methodology is presented to incorporate receptor flexibility in ligand docking and virtual screening. However, the systematic representation of the deformation space grows geometrically with the number of modes, and furthermore, midscale loop rearrangements like those found in protein kinase binding pockets cannot be accounted for with the first lowest-frequency modes. We thus introduced a measure of relevance of normal modes on a given region of interest and showed that only very few modes in the low-frequency range are necessary and sufficient to describe loop flexibility in cAMP-dependent protein kinase. We used this approach to generate an ensemble of representative receptor backbone conformations by perturbing the structure along a combination of relevant modes. Each ensemble conformation is complexed with known non-native binders to optimize the position of the binding-pocket side chains through a full flexible docking procedure. The multiple receptor conformations thus obtained are used in a small-scale virtual screening using receptor ensemble docking. We evaluated this algorithm on holo and apo structures of cAMP-dependent protein kinase that exhibit backbone rearrangements on two independent loop regions close to the binding pocket. Docking accuracy is improved, since the ligands considered in the virtual screening docked within 1.5 angstrom to at least one of the structures. The discrimination between binders and nonbinders is also enhanced, as shown by the improvement of the enrichment factor. This constitutes a new step toward the systematic integration of flexible ligand-flexible receptor docking tools in structure-based drug discovery.