As the number of structurally resolved protein-ligand complexes increases, the ligand-binding pockets of many proteins have been found to accommodate multiple different compounds. Effective use of these structural data is important for developing virtual screening (VS) methods that identify bioactive compounds. Here, we introduce a VS method, VS-APPLE (Virtual Screening Algorithm using Promiscuous Protein-Ligand complExes), based on promiscuous protein-ligand binding structures. In VS-APPLE, multiple ligands bound to a pocket are combined into a query template for screening. Both the structural match between a test compound and the multiple-ligand template and the possible collisions between the test compound and the target protein are evaluated by an efficient geometric hashing method. The performance of VS-APPLE was examined on a filtered, clustered version of the Directory of Useful Decoys data set. In Area Under the Curve analyses of this data set, VS-APPLE outperformed several popular screening programs. Judging from the performance of VS-APPLE, the structural data of promiscuous protein-ligand bindings could be further analyzed and exploited for developing VS methods.