Organoselenocyanates have attracted considerable attention in recent years due to their therapeutic potential and versatility in medicinal chemistry. Here, we report on the mechanism of inhibition by 5-phenylcarbamoylpentyl selenocyanide (SelSA-2), an analogue of the well-characterized histone deacetylase inhibitor suberoylanilide hydroxamic acid (SAHA, a.k.a. Vorinostat). We show that histone deacetylases 6 and 10 promote selenocyanate hydrolysis to generate a selenolate anion, and we explore the redox chemistry of selenium as it modulates inhibitory activity through reversible formation of the diselenide. The 2.15 Å-resolution crystal structure of histone deacetylase 6 cocrystallized with SelSA-2 conclusively demonstrates that it is not the selenocyanate, but instead a zinc-bound selenolate anion, that is the active pharmacophore responsible for enzyme inhibition.