Multidrug resistance (MDR), which is a significant impediment to the success of cancer chemotherapy, is attributable to the overexpression of membrane transport proteins, such as P-glycoprotein (P-gp), resulting in an increased drug efflux. In this study, we show that the histone deacetylase (HDAC) inhibitor apicidin leads to resistance of HeLa cells to paclitaxel through the induction of P-gp expression. Furthermore, apicidin dramatically increases the release of a fluorescent P-gp substrate, rhodamine 123, from cells. In parallel, apicidin resistance to the apoptotic potential of paclitaxel is associated with induction of P-gp expression in HeLa cells, as evidenced by specific inhibition of P-gp function using either the pharmacological inhibitor verapamil or RNA silencing. We also demonstrate the contribution of apicidin-induced functional P-gp expression to drug resistance using KB cells. Failure of P-gp induction by apicidin does not reverse paclitaxel-induced cytotoxicity in the cells. Although HDAC inhibitors are widely appreciated as a new class of anti-tumor agent, our findings clearly demonstrate that apicidin treatment may lead to P-gp-mediated resistance to other anti-tumor agents, suggesting a need for careful design of clinical applications using HDAC inhibitors.