Ataxia telangiectasia is a neurodegenerative disease caused by mutation of the Atm gene. Here we report that ataxia telangiectasia mutated (ATM) deficiency causes nuclear accumulation of histone deacetylase 4 (HDAC4) in neurons and promotes neurodegeneration. Nuclear HDAC4 binds to chromatin, as well as to myocyte enhancer factor 2A (MEF2A) and cAMP-responsive element binding protein (CREB), leading to histone deacetylation and altered neuronal gene expression. Blocking either HDAC4 activity or its nuclear accumulation blunts these neurodegenerative changes and rescues several behavioral abnormalities of ATM-deficient mice. Full rescue of the neurodegeneration, however, also requires the presence of HDAC4 in the cytoplasm, suggesting that the ataxia telangiectasia phenotype results both from a loss of cytoplasmic HDAC4 as well as its nuclear accumulation. To remain cytoplasmic, HDAC4 must be phosphorylated. The activity of the HDAC4 phosphatase, protein phosphatase 2A (PP2A), is downregulated by ATM-mediated phosphorylation. In ATM deficiency, enhanced PP2A activity leads to HDAC4 dephosphorylation and the nuclear accumulation of HDAC4. Our results define a crucial role of the cellular localization of HDAC4 in the events leading to ataxia telangiectasia neurodegeneration.