Polyamines are a ubiquitous class of polycationic small molecules that can influence gene expression by binding to nucleic acids. Reversible polyamine acetylation regulates nucleic acid binding and is required for normal cell cycle progression and proliferation. Here, we report the structures of Mycoplana ramosa acetylpolyamine amidohydrolase (APAH) complexed with a transition state analogue and a hydroxamate inhibitor and an inactive mutant complexed with two acetylpolyamine substrates. The structure of APAH is the first of a histone deacetylase-like oligomer and reveals that an 18-residue insert in the L2 loop promotes dimerization and the formation of an 18 Å long "L"-shaped active site tunnel at the dimer interface, accessible only to narrow and flexible substrates. The importance of dimerization for polyamine deacetylase function leads to the suggestion that a comparable dimeric or double-domain histone deacetylase could catalyze polyamine deacetylation reactions in eukaryotes.