Although histone deacetylase inhibitors (HDACis) are emerging as a new class of anticancer agents, the mechanism of tumor-selective killing by HDACi is not well understood. We used suppression of mortality by antisense rescue technique (SMART) to screen the key genes responsible for the tumor-selective killing by trichostatin A (TSA). Twenty-four genes were identified, the most significant of which was ubiquitin B (UbB). The expression of UbB was selectively upregulated by TSA in tumor cells, but not non-malignant cells. Further observation indicated that TSA induced a substantial dissipation of mitochondrial transmembrane potential, release of cytochrome c into the cytosol, and proteolytic cleavage of caspases-3/9 in HeLa cells, which was apparently mediated by ubiquitylation and the subsequent degradation of mitochondrial membrane proteins including BCL-2 and MCL-1. In contrast, knockdown of UbB expression inhibited the TSA-induced apoptotic cascade by abolishing TSA-induced ubiquitylation and the subsequent degradation of mitochondrial membrane proteins. Furthermore, apicidine, another HDACi, exhibited activity similar to that of TSA. Interestingly, TSA induced UbB-dependent proteasomal degradation of BCR-ABL fusion protein in K562 leukemic cells. Thus, our findings highlight the essential role of UbB and UbB-dependent proteasomal protein degradation in HDACi-induced tumor selectivity. The mechanism provides a novel starting point for dissecting the molecular mechanism underlying the tumor selectivity of HDACi.