The interplay between hypoxia-inducible factor-1alpha (HIF-1alpha) and histone deacetylase (HDACs) have been well studied; however, the mechanism of cross-talk is unclear. Here, we investigated the roles of HDAC4 and HDAC5 in the regulation of HIF-1alpha function and its associated mechanisms. HDAC4 and HDAC5 enhanced transactivation by HIF-1alpha without stabilizing HIF-1alpha. HDAC4 and HDAC5 physically associated with HIF-1alpha through the inhibitory domain (ID) that is the binding site for factor inhibiting HIF-1 (FIH-1). In the presence of these HDACs, binding of HIF-1alpha to FIH-1 decreased, whereas binding to p300 increased. These results indicate that HDAC4 and HDAC5 increase the transactivation function of HIF-1alpha by promoting dissociation of HIF-1alpha from FIH-1 and association with p300.