Class IIa histone deacetylases (HDACs) regulate the activity of many transcription factors to influence liver gluconeogenesis and the development of specialized cells including muscle, neurons and lymphocytes. Here we describe a conserved role for class IIa HDACs in sustaining robust circadian behavioral rhythms in Drosophila and cellular rhythms in mammalian cells. In mouse fibroblasts, over-expression of HDAC5 severely disrupts transcriptional rhythms of core clock genes. HDAC5 over-expression decreases BMAL1 acetylation on Lys537 and pharmacological inhibition of Class IIa HDACs increases BMAL1 acetylation. Furthermore, we observe cyclical nucleocytoplasmic shuttling of HDAC5 in mouse fibroblasts that is characteristically circadian. Mutation of the Drosophila homolog HDAC4 impairs locomotor activity rhythms of flies and decreases period mRNA levels. RNAi-mediated knockdown of HDAC4 in Drosophila clock cells also dampens circadian function. Given that the localization of Class IIa HDACs is signal-regulated and influenced by Ca2+ and cAMP signals, our findings offer a mechanism by which extracellular stimuli that generate these signals can feed into the molecular clock machinery.