Dual-specificity phosphatases (DSPs) are important, but poorly understood, cell signaling enzymes that remove phosphate groups from tyrosine and serine/threonine residues on their substrate. Deregulation of DSPs has been implicated in cancer, obesity, diabetes, inflammation, and Alzheimer's disease. Due to their biological and biomedical significance, DSPs have increasingly become the subject of drug discovery high-throughput screening (HTS) and focused compound library development efforts. Progress in identifying selective and potent DSP inhibitors has, however, been restricted by the lack of sufficient structural data on inhibitor-bound DSPs. The shallow, almost flat, substrate binding sites in DSPs have been a major factor in hampering the rational design and the experimental development of active site inhibitors. Recent experimental and virtual HTS studies, as well as advances in molecular modeling, provide new insights into the potential mechanisms for substrate recognition and binding by this important class of enzymes. We present herein an overview of the progress, along with a brief description of applications to two types of DSPs: Cdc25 and MAP kinase phosphatase (MKP) family members. In particular, we focus on combined computational and experimental efforts for designing Cdc25B and MKP-1 inhibitors and understanding their mechanisms of interactions with their target proteins. These studies emphasize the utility of developing computational models and methods that meet the two major challenges currently faced in structure-based in silico design of lead compounds: the conformational flexibility of the target protein and the entropic contribution to the selection and stabilization of particular bound conformers.