Lysine acetylation is a common post-translational modification of histone and non-histone proteins. This process has an important function in regulating transcriptional activities and other biological processes. Although several computer programs have been developed to predict protein acetylation sites, deacetylases responsible for known or predicted acetylation sites remain unknown. In this research, Class I histone deacetylases (HDACs) substrates were manually obtained, and sequence features of deacetylation sites were analyzed. We found that three members of Class I HDACs (HDAC1, HDAC2 and HDAC3) shared similar sequence features. Therefore, a method was proposed to identify the substrates of Class I HDACs. We evaluated the efficiency of the prediction based on P-value distribution analysis and leave-one-out test. To validate the result of the prediction, we overexpressed Class I HDACs in cells and detected the acetylation levels of potential substrates. In the experiment, five of the seven predicted proteins were deacetylated by Class I HDACs. These results suggested that our method could effectively predict protein deacetylation sites. The work has been integrated to the website ASEB, which was freely available at http://cmbi.bjmu.edu.cn/huac. 