Therapy of acute myeloid leukemia (AML) is unsatisfactory. Histone deacetylase inhibitors (HDACi) are active against leukemic cells in vitro and in vivo. Clinical data suggest further testing of such epigenetic drugs and to identify mechanisms and markers for their efficacy. Primary and permanent AML cells were screened for viability, replication stress/DNA damage, and regrowth capacities after single exposures to the clinically used pan-HDACi panobinostat (LBH589), the class I HDACi entinostat/romidepsin (MS-275/FK228), the HDAC3 inhibitor RGFP966, the HDAC6 inhibitor marbostat-100, the non-steroidal anti-inflammatory drug (NSAID) indomethacin, and the replication stress inducer hydroxyurea (HU). Immunoblotting was used to test if HDACi modulate the leukemia-associated transcription factors beta-catenin, Wilms tumor (WT1), and myelocytomatosis oncogene (MYC). RNAi was used to delineate how these factors interact. We show that LBH589, MS-275, FK228, RGFP966, and HU induce apoptosis, replication stress/DNA damage, and apoptotic fragmentation of beta-catenin. Indomethacin destabilizes beta-catenin and potentiates anti-proliferative effects of HDACi. HDACi attenuate WT1 and MYC caspase-dependently and -independently. Genetic experiments reveal a cross-regulation between MYC and WT1 and a regulation of beta-catenin by WT1. In conclusion, reduced levels of beta-catenin, MYC, and WT1 are molecular markers for the efficacy of HDACi. HDAC3 inhibition induces apoptosis and disrupts tumor-associated protein expression.