Previous findings have suggested that class IIa histone deacetylases (HDACs) (HDAC4, -5, -7, and -9) are inactive on acetylated substrates, thus differing from class I and IIb enzymes. Here, we present evidence supporting this view and demonstrate that class IIa HDACs are very inefficient enzymes on standard substrates. We identified HDAC inhibitors unable to bind recombinant human HDAC4 while showing inhibition in a typical HDAC4 enzymatic assay, suggesting that the observed activity rather reflects the involvement of endogenous copurified class I HDACs. Moreover, an HDAC4 catalytic domain purified from bacteria was 1,000-fold less active than class I HDACs on standard substrates. A catalytic Tyr is conserved in all HDACs except for vertebrate class IIa enzymes where it is replaced by His. Given the high structural conservation of HDAC active sites, we predicted the class IIa His-Nε2 to be too far away to functionally substitute the class I Tyr-OH in catalysis. Consistently, a Tyr-to-His mutation in class I HDACs severely reduced their activity. More importantly, a His-976-Tyr mutation in HDAC4 produced an enzyme with a catalytic efficiency 1,000-fold higher than WT, and this “gain of function phenotype” could be extended to HDAC5 and -7. We also identified trifluoroacetyl-lysine as a class IIa-specific substrate in vitro. Hence, vertebrate class IIa HDACs may have evolved to maintain low basal activities on acetyl-lysines and to efficiently process restricted sets of specific, still undiscovered natural substrates.