Hypoxia-inducible factor 1 alpha (HIF-1 alpha) plays a critical role in transcriptional gene activation involved in tumor angiogenesis. A novel class of agents, the histone deacetylase (HDAC) inhibitors, has been shown to inhibit tumor angiogenesis and HIF-1 alpha protein expression. However, the molecular mechanism responsible for this inhibition remains to be elucidated. In the current study, we investigated the molecular link between HIF-1 alpha inhibition and HDAC inhibition. Treatment of the VHL-deficient human renal cell carcinoma cell line UMRC2 with the hydroxamic HDAC inhibitor LAQ824 resulted in a dose-dependent inhibition of HIF-1 alpha protein via a VHL-independent mechanism and reduction of HIF-1 alpha transcriptional activity. HIF-1 alpha inhibition by LAQ824 was associated with HIF-1 alpha acetylation and polyubiquitination. HIF-1 alpha immunoprecipitates contained HDAC activity. Then, we tested different classes of HDAC inhibitors with diverse inhibitory activity of class I versus class II HDACs and assessed their capability of targeting HIF-1 alpha. Hydroxamic acid derivatives with known activity against both class I and class II HDACs were effective in inhibiting HIF-1 alpha at low nanomolar concentrations. In contrast, valproic acid and trapoxin were able to inhibit HIF-1 alpha only at concentrations that are effective against class II HDACs. Coimmunoprecipitation studies showed that class II HDAC4 and HDAC6 were associated with HIF-1 alpha protein. Inhibition by small interfering RNA of HDAC4 and HDAC6 reduced HIF-1 alpha protein expression and transcriptional activity. Taken together, these results suggest that class II HDACs are associated with HIF-1 alpha stability and provide a rationale for targeting HIF-1 alpha with HDAC inhibitors against class II isozymes.