Proteasomes are attractive emerging targets for anti-cancer therapies. Auranofin (Aur), a gold-containing compound clinically used to treat rheumatic arthritis, was recently approved by US Food and Drug Administration for Phase II clinical trial to treat cancer but its anti-cancer mechanism is poorly understood. Here we report that (i) Aur shows proteasome-inhibitory effect that is comparable to that of bortezomib/Velcade (Vel); (ii) different from bortezomib, Aur inhibits proteasome-associated deubiquitinases (DUBs) UCHL5 and USP14 rather than the 20S proteasome; (iii) inhibition of the proteasome-associated DUBs is required for Aur-induced cytotoxicity; and (iv) Aur selectively inhibits tumor growth in vivo and induces cytotoxicity in cancer cells from acute myeloid leukemia patients. This study provides important novel insight into understanding the proteasome-inhibiting property of metal-containing compounds. Although several DUB inhibitors were reported, this study uncovers the first drug already used in clinic that can inhibit proteasome-associated DUBs with promising anti-tumor effects.