Histone deacetylases (HDACs) are major epigenetic modulators involved in a broad spectrum of human diseases including cancers. Administration of HDAC inhibitors (HDACis) leads to growth inhibition, differentiation, and apoptosis of cancer cells. Understanding the regulatory mechanism of HDACs is imperative to harness the therapeutic potentials of HDACis. Here we show that HDACi- and DNA damage-induced apoptosis are severely compromised in mouse embryonic fibroblasts lacking a HECT domain ubiquitin ligase, Mule (Mcl-1 ubiquitin ligase E3). Mule specifically targets HDAC2 for ubiquitination and degradation. Accumulation of HDAC2 in Mule-deficient cells leads to compromised p53 acetylation as well as crippled p53 transcriptional activation, accumulation, and apoptotic response upon DNA damage and Nutlin-3 treatments. These defects in Mule-null cells can be partially reversed by HDACis and fully rescued by lowering the elevated HDAC2 in Mule-null cells to the normal levels as in wild-type cells. Taken together, our results reveal a critical regulatory mechanism of HDAC2 by Mule and suggest this pathway determines the cellular response to HDACis and DNA damage.