CDC25 phosphatases play critical roles in cell cycle regulation and are attractive targets for anticancer therapies. Several small non-peptide molecules are known to inhibit CDC25, but many of them appear to form a covalent bond with the enzyme or act through oxidation of the thiolate group of the catalytic cysteine. Structure-based virtual ligand screening computations were performed with FRED, Surflex, and LigandFit, a compound collection of over 310,000 druglike molecules and the crystal structure of CDC25B in order to identify novel classes of ligands. In vitro experiments carried out on a selected list of 1500 molecules led to the discovery of 99 compounds able to inhibit CDC25B activity at 100 µM. Further docking computations were applied, allowing us to propose a binding mode for the most potent molecule (IC50 = 13 µM). Our best compounds represent promising new classes of CDC25 inhibitors that also exhibit antiproliferative properties.