Despite the recently growing interest in the acetylation of lysine residues by prokaryotic enzymes, the underlying biological function is still not well understood. Deacetylation is accomplished by proteins that belong to the histone deacetylase (HDAC) superfamily. In this report, we present the first crystal structure of PA3774, a histone deacetylase homologue from the human pathogen Pseudomonas aeruginosa that shares a high degree of homology with class IIb HDACs. We determined the crystal structure of the ligand-free enzyme and protein-ligand complexes with a trifluoromethylketone inhibitor and the reaction product acetate. Moreover, we produced loss of function mutants and determined the structure of the inhibitor-free PA3774H143A mutant, the inhibitor-free PA3774Y313F mutant, and the PA3774Y313F mutant in complex with the highly selective hydroxamate inhibitor PFSAHA. The overall structure reveals that the exceptionally long L1 loop mediates the formation of a tetramer composed of two "head-to-head" dimers. The distinctive dimer interface significantly confines the entrance area of the active site, suggesting a crucial role for substrate recognition and selectivity.