The reduced ability of the central nervous system to regenerate with increasing age limits functional recovery following demyelinating injury. Previous work has shown that myelin debris can overwhelm the metabolic capacity of microglia, thereby impeding tissue regeneration in aging, but the underlying mechanisms are unknown. In a model of demyelination, we found that a substantial number of genes that were not effectively activated in aged myeloid cells displayed epigenetic modifications associated with restricted chromatin accessibility. Ablation of two class I histone deacetylases in microglia was sufficient to restore the capacity of aged mice to remyelinate lesioned tissue. We used Bacillus Calmette-Guerin (BCG), a live-attenuated vaccine, to train the innate immune system and detected epigenetic reprogramming of brain-resident myeloid cells and functional restoration of myelin debris clearance and lesion recovery. Our results provide insight into aging-associated decline in myeloid function and how this decay can be prevented by innate immune reprogramming.