Dual specificity protein phosphatase 4 (DUSP4) has been considered a promising target for the development of therapeutics for various human cancers. Here, we report the first example for a successful application of the structure-based virtual screening to identify the novel small-molecule DUSP4 inhibitors. As a consequence of the virtual screening with the modified scoring function to include an effective molecular solvation free energy term, five micromolar DUSP4 inhibitors are found with the associated $IC_{50}$ values ranging from 3.5 to $10.8{mu}M$. Because these newly identified inhibitors were also screened for having desirable physicochemical properties as a drug candidate, they may serve as a starting point of the structure-activity relationship study to optimize the medical efficacy. Structural features relevant to the stabilization of the new inhibitors in the active site of DUSP4 are discussed in detail.