In C2C12 myoblasts, endogenous histone deacetylase HDAC4 shuttles between cytoplasmic and nuclear compartments, supporting the hypothesis that its subcellular localization is dynamically regulated. However, upon differentiation, this dynamic equilibrium is disturbed and we find that HDAC4 accumulates in the nuclei of myotubes, suggesting a positive role of nuclear HDAC4 in muscle differentiation. Consistent with the notion of regulation of HDAC4 intracellular trafficking, we reveal that HDAC4 contains a modular structure consisting of a C-terminal autonomous nuclear export domain, which, in conjunction with an internal regulatory domain responsive to calcium/calmodulin-dependent protein kinase IV (CaMKIV), determines its subcellular localization. CaMKIV phosphorylates HDAC4 in vitro and promotes its nuclear-cytoplasmic shuttling in vivo. However, although 14-3-3 binding of HDAC4 has been proposed to be important for its cytoplasmic retention, we find this interaction to be independent of CaMKIV. Rather, the HDAC4.14-3-3 complex exists in the nucleus and is required to confer CaMKIV responsiveness. Our results suggest that the subcellular localization of HDAC4 is regulated by sequential phosphorylation events. The first event is catalyzed by a yet to be identified protein kinase that promotes 14-3-3 binding, and the second event, involving protein kinases such as CaMKIV, leads to efficient nuclear export of the HDAC4.14-3-3 complex.