HDAC4 (histone deacetylase 4) belongs to class IIa of histone deacetylases, which groups important regulators of gene expression, controlling pleiotropic cellular functions. Here we show that, in addition to the well-defined nuclear/cytoplasmic shuttling, HDAC4 activity is modulated by the ubiquitin–proteasome system. Serum starvation elicits the poly-ubiquitination and degradation of HDAC4 in nontransformed cells. Phosphorylation of serine 298 within the PEST1 sequence plays an important role in the control of HDAC4 stability. Serine 298 lies within a glycogen synthase kinase 3β consensus sequence, and removal of growth factors fails to trigger HDAC4 degradation in cells deficient in this kinase. GSK3β can phosphorylate HDAC4 in vitro, and phosphorylation of serine 302 seems to play the role of priming phosphate. We have also found that HDAC4 modulates random cell motility possibly through the regulation of KLF2 transcription. Apoptosis, autophagy, cell proliferation, and growth arrest were unaffected by HDAC4. Our data suggest a link between regulation of HDAC4 degradation and the control of cell motility as operated by growth factors.