Bacteria communicate by means of small signal molecules in a process termed quorum sensing (QS). QS enables bacteria to organize their activities at the population level, including the coordinated secretion of virulence factors. Certain small-molecule compounds, known as quorum-sensing inhibitors (QSIs), have been shown to effectively block QS and subsequently attenuate the virulence of Pseudomonas aeruginosa, as well as increasing its susceptibility to both antibiotics and the immune system. In this study, a structure-based virtual screening (SB-VS) approach was used for the discovery of novel QSI candidates. Three-dimensional structures of 3,040 natural compounds and their derivatives were obtained, after which molecular docking was performed using the QS receptor LasR as a target. Based on docking scores and molecular masses, 22 compounds were purchased to determine their efficacies as quorum-sensing inhibitors. Using a live reporter assay for quorum sensing, 5 compounds were found to be able to inhibit QS-regulated gene expression in P. aeruginosa in a dose-dependent manner. The most promising compound, G1, was evaluated by isobaric tag for relative and absolute quantitation (iTRAQ)-based proteomic analysis, and it was found to significantly affect the abundance of 46 proteins (19 were upregulated; 27 were downregulated) in P. aeruginosa PAO1. It specifically reduced the expression of several quorum-sensing-regulated virulence factors, such as protease IV, chitinase, and pyoverdine synthetases. G1 was also able to reduce extracellular DNA release and inhibited the secretion of the virulence factor, elastase, whose expression is regulated by LasR. These results demonstrate the utility of SB-VS for the discovery of target-specific QSIs.