The prognosis of metastatic or relapsed rhabdomyosarcoma (RMS) is poor, highlighting the need of new treatment options. In the present study, we evaluated the in vitro efficacy of arsenic trioxide (ATO) in RMS, a FDA-approved drug used in pediatric leukemia. Here, we report that ATO exerts antitumor activity against RMS cells both as single agent and in combination with microtubule-targeting drugs. Monotherapy with ATO reduces cell viability, triggers apoptosis and suppresses clonogenic survival of RMS cells, at least in part, by transcriptional induction of the proapoptotic BH3-only protein Noxa. siRNA-mediated knockdown of Noxa significantly rescues ATO-mediated cell death, demonstrating that Noxa is required for cell death. Also, ATO suppresses endogenous Hedgehog (Hh) signaling, as it significantly reduces Gli1 transcriptional activity and expression levels of several Hh target genes. Furthermore, we identify synergistic induction of apoptosis by ATO together with several antimicrotubule agents including vincristine (VCR), vinblastine and eribulin. The addition of the broad-range caspase inhibitor zVAD.fmk or overexpression of the antiapoptotic protein Bcl-2 significantly reduce ATO/VCR-induced cell death, indicating that the ATO/VCR combination triggers caspase-dependent apoptosis via the mitochondrial pathway. In summary, ATO exerts antitumor activity against RMS, especially in combination with antimicrotubule drugs. These findings have important implications for the development of novel therapeutic strategies for RMS.