Prostate cancer (PCa), a leading cause of cancer-related death in men, becomes resistant to androgen deprivation therapy by inducing androgen receptor (AR) activity, which is known as castration-resistant PCa (CRPC). Enzalutamide is an approved drug that inhibits AR activity and increases overall survival. However, resistance to enzalutamide develops rapidly often by increasing AR activity, suggesting that new therapies are required for CRPC. We investigated whether betulinic acid (BA), a small molecule from plants that inhibits multiple deubiquitinases (DUBs), reduces AR, and selectively kills PCa cells, can provide an adjuvant strategy for CRPC. Our data indicated that BA reduced AR protein stability and mRNA expression, making it an attractive agent for CRPC. BA decreased AR mRNA possibly by inhibiting a histone 2A DUB thereby increasing ubiquitinated histone 2A, a transcriptional repressor. We identified multiple and specific DUBs inhibited by BA either in PCa cells or using recombinant DUBs. Similar results were obtained using another multi-DUB inhibitor WP1130, suggesting that these DUB inhibitors can decrease AR expression and increase PCa-specific death. Our results also suggest that combining multi-DUB inhibitors BA or WP1130 with enzalutamide may provide a novel strategy for CRPC by further decreasing AR expression and increasing apoptotic cell death.