In neurons, dynamic changes in the subcellular localization of histone deacetylases (HDACs) are thought to contribute to signal-regulated gene expression. Here we show that in mouse hippocampal neurons, synaptic activity-dependent nucleo-cytoplasmic shuttling is a common feature of all members of class IIa HDACs, which distinguishes them from other classes of HDACs. Nuclear calcium, a key regulator in neuronal gene expression, is required for the nuclear export of a subset of class IIa HDACs. We found that inhibition of nuclear calcium signaling using CaMBP4 or increasing the nuclear calcium buffering capacity by means of expression of a nuclear targeted version of parvalbumin (PV.NLS-mC) led to a build-up of HDAC4 and HDAC5 in the cell nucleus, which in the case of PV.NLS-mC can be reversed by nuclear calcium transients triggered by bursts of action potential firing. A similar nuclear accumulation of HDAC4 and HDAC5 was observed in vivo in the mouse hippocampus following stereotaxic delivery of recombinant adeno-associated viruses expressing either CaMBP4 or PV.NLS-mC. The modulation of HDAC4 activity either by RNA interference-mediated reduction of HDAC4 protein levels or by expression of a constitutively nuclear localized mutant of HDAC4 leads to changes in the mRNA levels of several nuclear calcium-regulated genes with known functions in acquired neuroprotection (atf3, serpinb2), memory consolidation (homer1, arc), and the development of chronic pain (ptgs2, c1qc). These results identify nuclear calcium as a regulator of nuclear export of HDAC4 and HDAC5. The reduction of nuclear localized HDACs represents a novel transcription-promoting pathway stimulated by nuclear calcium.