A number of drugs developed against cancer-specific molecular targets have been shown to offer survival benefits alone or in combination with standard treatments, especially for those cases in which tumor pathogenesis is dominated by a single molecular abnormality. One example for such a tumor type is alveolar rhabdomyosarcoma (aRMS), which is characterized by a specific translocation creating the oncogenic PAX3/FKHR transcription factor, believed to be the molecular basis of the disease. Recently, we were able to show that the small molecule inhibitor PKC412 (midostaurin) shows strong antitumor activity against aRMS by reducing the transcriptional activity of PAX3/FKHR. In this study, we screened for combination strategies that are superior to PKC412-only treatment and found that the combination of PKC412 with histone deacetylase inhibitors like valproic acid (VPA) synergistically induced apoptosis resulting in suppressed aRMS tumor growth in vivo. We provide evidence that the antitumor effect on combination treatment is achieved by VPA-induced reactivation of p21, which is downregulated in aRMS cells by destabilization of the transcriptional regulator EGR1 by PAX3/FKHR. Our study highlights a possible mechanism behind the increased efficacy and indicates that different arms of PAX3/FKHR oncogenicity can be exploited therapeutically by the specific combination of drugs to increase their therapeutic potential.