Searches of several sequence databases reveal that human HD1, yeast HDA1, yeast RPD3 and other eukaryotic histone deacetylases share nine motifs with archaeal and eubacterial enzymes, including acetoin utilization protein (acuC) and acetylpolyamine amidohydrolase. Histone deacetylase and acetylpolyamine amidohydrolase also share profound functional similarities in that both: (i) recognize an acetylated aminoalkyl group; (ii) catalyze the removal of the acetyl group by cleaving an amide bond; (iii) increase the positive charge of the substrate. Stabilization of nucleosomal DNA-histone interaction brought about by the change in charge has been implicated as the underlying cause for histone deacetylase-mediated transcriptional repression. We speculate that the eukaryotic histone deacetylases originated from a prokaryotic enzyme similar to the acetylpolyamine amidohydrolases that relied on reversible acetylation and deacetylation of the aminoalkyl group of a DNA binding molecule to achieve a gene regulatory effect.