Histone deacetylases (HDACs) mediate changes in nucleosome conformation and are important in the regulation of gene expression. HDACs are involved in cell-cycle progression and differentiation, and their deregulation is associated with several cancers. HDAC inhibitors, such as trichostatin A (TSA) and suberoylanilide hydroxamic acid (SAHA), have anti-tumour effects, as they can inhibit cell growth, induce terminal differentiation and prevent the formation of tumours in mice models, and they are effective in the treatment of promyelocytic leukemia. Here we describe the structure of the histone deacetylase catalytic core, as revealed by the crystal structure of a homologue from the hyperthermophilic bacterium Aquifex aeolicus, that shares 35.2% identity with human HDAC1 over 375 residues, deacetylates histones in vitro and is inhibited by TSA and SAHA. The deacetylase, deacetylase-TSA and deacetylase-SAHA structures reveal an active site consisting of a tubular pocket, a zinc-binding site and two Asp-His charge-relay systems, and establish the mechanism of HDAC inhibition. The residues that make up the active site and contact the inhibitors are conserved across the HDAC family. These structures also suggest a mechanism for the deacetylation reaction and provide a framework for the further development of HDAC inhibitors as antitumour agents.