Reversible protein acetylation is established as a modification of major regulatory significance. In particular, histone acetylation regulates access to genetic information in eukaryotes. For example, class I and class II histone deacetylases are regulatory components of corepressor complexes involved in cell cycle progression and differentiation. Here, we have investigated the function of such enzymes in Trypanosoma brucei, mono-flagellated parasitic protozoa that branched very early from the eukaryotic lineage. Four T. brucei genes encoding histone deacetylase orthologues have been identified, cloned and characterized. The predicted deacetylases, DAC1-4 are approximately 43, 61, 75 and 64 kDa respectively. They share significant similarity with mammalian and yeast class I (DAC1 and DAC2) and class II (DAC3 and DAC4) histone deacetylases, and all except DAC2 have the critical residues predicted to be required for deacetylase activity. In gene targeting experiments, DAC1 and DAC3 appear to be essential whereas DAC2 and DAC4 are not required for viability. Of the two mutant cell types, the dac4 mutant displays a delay in the G2/M phase of the cell cycle. Our results provide genetic validation of DAC1 and DAC3 as potential chemotherapy targets and demonstrate that T. brucei expresses at least three probable histone deacetylases with distinct function.