Cationic polyamines such as spermidine and spermine are critical in all forms of life, as they regulate the function of biological macromolecules. Intracellular polyamine metabolism is regulated by reversible acetylation and dysregulated polyamine metabolism is associated with neoplastic diseases such as colon cancer, prostate cancer and neuroblastoma. Here we report that histone deacetylase 10 (HDAC10) is a robust polyamine deacetylase, using recombinant enzymes from Homo sapiens (human) and Danio rerio (zebrafish). The 2.85 Å-resolution crystal structure of zebrafish HDAC10 complexed with a transition-state analogue inhibitor reveals that a glutamate gatekeeper and a sterically constricted active site confer specificity for N8-acetylspermidine hydrolysis and disfavour acetyllysine hydrolysis. Both HDAC10 and spermidine are known to promote cellular survival through autophagy. Accordingly, this work sets a foundation for studying the chemical biology of autophagy through the structure-based design of inhibitors that may also serve as new leads for cancer chemotherapy.