Therapy resistance represents a major problem for disease management in oncology. Histone deacetylase inhibitors (HDACi) have been shown to modulate the cell cycle, to induce apoptosis and to sensitize cancer cells for other chemotherapeutics. Our study shows that the HDACi valproic acid (VPA) and the ribonucleotide reductase inhibitor hydroxyurea (HU) potentiate the pro-apoptotic effects of each other towards several cancer cell lines. This correlates with the HU-induced degradation of the cyclin-dependent kinase inhibitors (CDKI) p21 and p27, mediated by the proteasome or caspase-3. Moreover, we found that caspase-3 activation is required for VPA-induced apoptosis. Remarkably, p21 and p27 can confer resistance against VPA and HU. Both CDKI interact with caspase-3 and compete with other caspase-3 substrates. Hence, p21 and p27 may contribute to chemotherapy resistance as apoptosis inhibitors. Since the biological effects of VPA and HU could be achieved at concentrations used in current treatment protocols, the combined application of these compounds might be considered as a potential strategy for cancer treatment.