DNA is the well-known molecular target of current platinum-based anticancer drugs; consequently, their clinical use is severely restricted by their systemic toxicities and drug resistance originating from non-selective DNA damage. Various strategies have been developed to circumvent the shortcomings of platinum-based chemotherapy but the inherent problem remains unsolved. Here we report that platinum pyrithione (PtPT), a chemically well-characterized synthetic complex of platinum, inhibits proteasome function and thereby exhibits greater and more selective cytotoxicity to multiple cancer cells than cisplatin, without showing discernible DNA damage both in vitro and in vivo. Moreover, unlike the classical proteasome inhibitor bortezomib/Velcade which inhibits the proteasome via blocking the peptidase activity of 20S proteasomes, PtPT primarily deactivates 26S proteasome-associated deubiquitinases USP14 and UCHL5. Furthermore, PtPT can selectively induce cytotoxicity and proteasome inhibition in cancer cells from leukemia patients but not peripheral blood mononuclear cells from healthy humans. In nude mice, PtPT also remarkably inhibited tumor xenograft growth, without showing the adverse effects that were induced by cisplatin. Hence, we have discovered a new platinum-based anti-tumor agent PtPT which targets 26S proteasome-associated deubiquitinases rather than DNA in the cell and thereby exerts safer and more potent anti-tumor effects, identifying a highly translatable new platinum-based anti-cancer strategy.