Class IIa histone deacetylases (HDACs 4/5/7/9) are transcriptional regulators with critical roles in cardiac disease and cancer. HDAC inhibitors are promising anticancer agents, and although they are known to disrupt mitotic progression, the underlying mechanisms of mitotic regulation by HDACs are not fully understood. Here we provide the first identification of histone deacetylases as substrates of Aurora B kinase (AurB). Our study identifies class IIa HDACs as a novel family of AurB targets and provides the first evidence that HDACs are temporally and spatially regulated by phosphorylation during the cell cycle. We define the precise site of AurB-mediated phosphorylation as a conserved serine within the nuclear localization signals of HDAC4, HDAC5, and HDAC9 at Ser265, Ser278, and Ser242, respectively. We establish that AurB interacts with these HDACs in vivo, and that this association increases upon disruption of 14-3-3 binding. We observe colocalization of endogenous, phosphorylated HDACs with AurB at the mitotic midzone in late anaphase and the midbody during cytokinesis, complemented by a reduction in HDAC interactions with components of the nuclear corepressor complex. We propose that AurB-dependent phosphorylation of HDACs induces sequestration within a phosphorylation gradient at the midzone, maintaining separation from re-forming nuclei and contributing to transcriptional control.