Zn2+-dependent histone deacetylases are widely distributed in archaea, bacteria, and eukaryotes. Through deacetylation of histones and other biomolecules, these enzymes regulate mammalian gene expression, microtubule stability, and polyamine metabolism. In plants, they play essential roles in development and stress response, but little is known about their biochemistry. We provide here a holistic revision of plant histone deacetylase (HDA) phylogeny and translate recent lessons from other organisms. HDA evolution correlates with a gain of structural ductility/disorder, as observed for other proteins. We also highlight two recently identified Brassicaceae-specific HDAs, as well as unprecedented key mutations that would affect the catalytic activity of individual HDAs. This revised phylogeny will contextualize future studies and illuminate research on plant development and adaptation.