The acetylation state of histones can influence transcription. Acetylation, carried out by acetyltransferases such as CBP/p300 and P/CAF, is commonly associated with transcriptional stimulation, whereas deacetylation, mediated by the three known human deacetylases HDAC1, 2 and 3, causes transcriptional repression. The known human deacetylases represent a single family and are homologues of the yeast RPD3 deacetylase. Here we identify and characterize HDAC4, a representative of a new human histone deacetylase family, which is homologous to the yeast HDA1 deacetylase. We show that HDAC4, unlike other deacetylases, shuttles between the nucleus and the cytoplasm in a process involving active nuclear export. In the nucleus, HDAC4 associates with the myocyte enhancer factor MEF2A. Binding of HDAC4 to MEF2A results in the repression of MEF2A transcriptional activation, a function that requires the deacetylase domain of HDAC4. These results identify MEF2A as a nuclear target for HDAC4-mediated repression and suggests that compartmentalization may be a novel mechanism for controlling the nuclear activity of this new family of deacetylases.