Members of the myocyte enhancer factor-2 (MEF2) family of transcription factors associate with myogenic basic helix-loop-helix transcription factors such as MyoD to activate skeletal myogenesis. MEF2 proteins also interact with the class II histone deacetylases HDAC4 and HDAC5, resulting in repression of MEF2-dependent genes. Execution of the muscle differentiation program requires release of MEF2 from repression by HDACs, which are expressed constitutively in myoblasts and myotubes. Here we show that HDAC5 shuttles from the nucleus to the cytoplasm when myoblasts are triggered to differentiate. Calcium/calmodulin-dependent protein kinase (CaMK) signalling, which stimulates myogenesis and prevents formation of MEF2-HDAC complexes, also induces nuclear export of HDAC4 and HDAC5 by phosphorylation of these transcriptional repressors. An HDAC5 mutant lacking two CaMK phosphorylation sites is resistant to CaMK-mediated nuclear export and acts as a dominant inhibitor of skeletal myogenesis, whereas a cytoplasmic HDAC5 mutant is unable to block efficiently the muscle differentiation program. Our results highlight a mechanism for transcriptional regulation through signal- and differentiation-dependent nuclear export of a chromatin-remodelling enzyme, and suggest that nucleo-cytoplasmic trafficking of HDACs is involved in the control of cellular differentiation.