Microtubule-mediated cellular events such as intracellular transport and the maintenance of cell polarity are highly dependent upon microtubule stability, which is controlled by a repertoire of microtubule-associated proteins (MAPs) in the cell. MAP7 domain-containing protein 3 (Mdp3) has recently been identified as a critical regulator of microtubule stability. However, it remains elusive how Mdp3 carries out this function. In this study, by examination of tubulin partitioning between the polymer and soluble dimer forms, we found that Mdp3 could protect microtubules from cold- or nocodazole-induced depolymerization. Immunoblotting and immunofluorescence microscopy showed that knockdown of Mdp3 expression significantly reduced the level of tubulin acetylation. In vitro tubulin polymerization assays revealed that the amino-terminal region of Mdp3 was necessary for its ability to stabilize microtubules. Immunoprecipitation and pulldown experiments showed that the amino-terminal region mediated the interaction of Mdp3 with histone deacetylase 6 (HDAC6), in addition to its association with tubulin and microtubules. Immunofluorescence microscopy further demonstrated that endogenous Mdp3 and HDAC6 colocalized in the cytoplasm. Moreover, depletion of Mdp3 dramatically increased the activity of HDAC6 toward tubulin deacetylation. These findings suggest that Mdp3 controls microtubule stability through its binding to tubulin and microtubules as well as its regulation of HDAC6 activity.