Purpose: Histone deacetylase inhibitors (HDACi) are epigenome-targeting small molecules approved for the treatment of cutaneous T-cell lymphoma and multiple myeloma. They have also demonstrated clinical activity in acute myelogenous leukemia, non–small cell lung cancer, and estrogen receptor–positive breast cancer, and trials are underway assessing their activity in combination regimens including immunotherapy. However, there is currently no clear strategy to reliably predict HDACi sensitivity. In colon cancer cells, apoptotic sensitivity to HDACi is associated with transcriptional induction of multiple immediate-early (IE) genes. Here, we examined whether this transcriptional response predicts HDACi sensitivity across tumor type and investigated the mechanism by which it triggers apoptosis. Experimental Design: Fifty cancer cell lines from diverse tumor types were screened to establish the correlation between apoptotic sensitivity, induction of IE genes, and components of the intrinsic apoptotic pathway. Results: We show that sensitivity to HDACi across tumor types is predicted by induction of the IE genes FOS, JUN, and ATF3, but that only ATF3 is required for HDACi-induced apoptosis. We further demonstrate that the proapoptotic function of ATF3 is mediated through direct transcriptional repression of the prosurvival factor BCL-XL (BCL2L1). These findings provided the rationale for dual inhibition of HDAC and BCL-XL, which we show strongly cooperate to overcome inherent resistance to HDACi across diverse tumor cell types. Conclusions: These findings explain the heterogeneous responses of tumor cells to HDACi-induced apoptosis and suggest a framework for predicting response and expanding their therapeutic use in multiple cancer types.