Bortezomib (Velcade) is used widely for the treatment of various human cancers; however, its mechanisms of action are not fully understood, particularly in myeloid malignancies. Bortezomib is a selective and reversible inhibitor of the proteasome. Paradoxically, we find that bortezomib induces proteasome-independent degradation of the TRAF6 protein, but not mRNA, in myelodysplastic syndrome (MDS) and acute myeloid leukemia (AML) cell lines and primary cells. The reduction in TRAF6 protein coincides with bortezomib-induced autophagy, and subsequently with apoptosis in MDS/AML cells. RNAi-mediated knockdown of TRAF6 sensitized bortezomib-sensitive and -resistant cell lines, underscoring the importance of TRAF6 in bortezomib-induced cytotoxicity. Bortezomib-resistant cells expressing an shRNA targeting TRAF6 were resensitized to the cytotoxic effects of bortezomib due to down-regulation of the proteasomal subunit α-1 (PSMA1). To determine the molecular consequences of loss of TRAF6 in MDS/AML cells, in the present study, we applied gene-expression profiling and identified an apoptosis gene signature. Knockdown of TRAF6 in MDS/AML cell lines or patient samples resulted in rapid apoptosis and impaired malignant hematopoietic stem/progenitor function. In summary, we describe herein novel mechanisms by which TRAF6 is regulated through bortezomib/autophagy-mediated degradation and by which it alters MDS/AML sensitivity to bortezomib by controlling PSMA1 expression.