The post-translational modification of histones plays an important role in chromatin regulation, a process that insures the fidelity of gene expression and other DNA transactions. Equally important as the enzymes that generate these modifications are the enzymes that remove them. Recent studies have identified some of the enzymes that remove histone modifications and have characterized their activities. In addition, structural and biochemical studies of these enzymes have focused on the histone lysine deacetylases HDAC8 and sirtuins, and on the arginine and lysine demethylases PAD and BHC110/LSD1, respectively. These new findings may be used as a context to present new information that contributes to our understanding of chromatin regulation, and to pose remaining questions pertaining to the activities of these enzymes and the roles they play in chromatin regulation.