CDC25 phosphatases play a critical role in the regulation of the cell cycle and thus represent attractive cancer therapeutic targets. We previously discovered the 4-(2-carboxybenzoyl)phthalic acid (NSC28620) as a new CDC25 inhibitor endowed with promising anticancer activity in breast, prostate, and leukemia cells. Herein, we report a structure-based optimization of NSC28620, leading to the identification of a series of novel naphthylphenylketone and naphthylphenylamine derivatives as CDC25B inhibitors. Compounds <b>7j</b>, <b>7i</b>, <b>6e</b>, <b>7f</b>, and <b>3</b> showed higher inhibitory activity than the initial lead, with <i>K</i><sub>i</sub> values in the low micromolar range. Kinetic analysis, intrinsic fluorescence studies, and induced fit docking simulations provided a mechanistic understanding of the activity of these derivatives. All compounds were tested in the highly aggressive human melanoma cell lines A2058 and A375. Compound <b>4a</b> potently inhibited cell proliferation and colony formation, causing an increase of the G2/M phase and a reduction of the G0/G1 phase of the cell cycle in both cell lines.