Histone acetylation and deacetylation at the N-terminus of histone tails play crucial roles in the regulation of eukaryotic gene activity. Histone acetylation and deacetylation are catalyzed by histone acetyltransferases and histone deacetylases (HDACs), respectively. A growing number of studies have demonstrated the importance of histone deacetylation/acetylation on genome stability, transcriptional regulation, development and response to stress in Arabidopsis. However, the biological functions of HDACs in tomato have not been investigated previously. Fifteen HDACs identified from tomato (Solanum lycopersicum) can be grouped into RPD3/HDA1, SIR2 and HD2 families based on phylogenetic analysis. Meanwhile, 10 members of the RPD3/HDA1 family can be further subdivided into four groups, namely Class I, Class II, Class III, and Class IV. High similarities of protein sequences and conserved domains were identified among SlHDACs and their homologs in Arabidopsis. Most SlHDACs were expressed in all tissues examined with different transcript abundance. Transient expression in Arabidopsis protoplasts showed that SlHDA8, SlHDA1, SlHDA5, SlSRT1 and members of the HD2 family were localized to the nucleus, whereas SlHDA3 and SlHDA4 were localized in both the cytoplasm and nucleus. The difference in the expression patterns and subcellular localization of SlHDACs suggest that they may play distinct functions in tomato. Furthermore, we found that three members of the RPD3/HDA1 family, SlHDA1, SIHDA3 and SlHDA4, interacted with TAG1 (TOMATO AGAMOUS1) and TM29 (TOMATO MADS BOX29), two MADS-box proteins associated with tomato reproductive development, indicating that these HDACs may be involved in gene regulation in reproductive development.