Class IIa histone deacetylases (HDACs) are found both in the cytoplasm and in the nucleus where they repress genes involved in several major developmental programs. In response to specific signals, the repressive activity of class IIa HDACs is neutralized through their phosphorylation on multiple N-terminal serine residues and 14-3-3-mediated nuclear exclusion. Here, we demonstrate that class IIa HDACs are subjected to signal-independent nuclear export that relies on their constitutive phosphorylation. We identify EMK and C-TAK1, two members of the microtubule affinity-regulating kinase (MARK)/Par-1 family, as regulators of this process. We further show that EMK and C-TAK1 phosphorylate class IIa HDACs on one of their multiple 14-3-3 binding sites and alter their subcellular localization and repressive function. Using HDAC7 as a paradigm, we extend these findings by demonstrating that signal-independent phosphorylation of the most N-terminal serine residue by the MARK/Par-1 kinases, i.e., Ser155, is a prerequisite for the phosphorylation of the nearby 14-3-3 site, Ser181. We propose that this multisite hierarchical phosphorylation by a variety of kinases allows for sophisticated regulation of class IIa HDACs function.