BACKGROUND: Histone deacetylases (HDACs) are involved in epigenetic gene regulation via deacetylation of acetylated lysine residues of both histone and non-histone proteins. Among the 18 HDACs identified in humans, HDAC8, a class I HDAC, is best understood structurally and enzymatically. However, its precise subcellular location, function in normal cellular physiology, its protein partners and substrates still remain elusive. METHODS: The subcellular localization of HDAC8 was studied using immunofluorescence and confocal imaging. The binding parterns were identified employing immunoprecipitation (IP) followed by MALDI-TOF analysis and confirmed using in-silico protein-protein interaction studies, HPLC-based in vitro deacetylation assay, intrinsic fluorescence spectrophotometric analysis, Circular dichroism (CD) and Surface Plasmon Resonance (SPR). Functional characterization of the binding was carried out using immunoblot and knockdown by siRNA. Using one way ANOVA statistical significance (n = 3) was determined. RESULTS: Here, we show that HDAC8 and its phosphorylated form (pHDAC8) localized predominantly in the cytoplasm in cancerous, HeLa, and non-cancerous (normal), HEK293T, cells, although nucleolar localization was observed in HeLa cells. The study identified Alpha tubulin as a novel interacting partner of HDAC8. Further, the results indicated binding and deacetylation of tubulin at ac-lys40 by HDAC8. Knockdown of HDAC8 by siRNA, inhibition of HDAC8 and/or HDAC6 by PCI-34051 and tubastatin respectively, cell-migration, cell morphology and cell cycle analysis clearly explained HDAC8 as tubulin deacetylase in HeLa cells and HDAC6 in HEK 293 T cells. CONCLUSIONS: HDAC8 shows functional redundancy with HDAC6 when overexpressed in cervical cancer cells, HeLa, and deacetylaes ac-lys40 of alpha tubulin leading to cervical cancer proliferation and progression.