Human histone deacetylase 6 (HDAC6) is the major deacetylase responsible for removing the acetyl group from Lys40 of α-tubulin (αK40), which is located lumenally in polymerized microtubules. Here, we provide a detailed kinetic analysis of tubulin deacetylation and HDAC6/microtubule interactions using individual purified components. Our data unequivocally show that free tubulin dimers represent the preferred HDAC6 substrate, with a K M value of 0.23 µM and a deacetylation rate over 1,500-fold higher than that of assembled microtubules. We attribute the lower deacetylation rate of microtubules to both longitudinal and lateral lattice interactions within tubulin polymers. Using TIRF microscopy, we directly visualized stochastic binding of HDAC6 to assembled microtubules without any detectable preferential binding to microtubule tips. Likewise, indirect immunofluorescence microscopy revealed that microtubule deacetylation by HDAC6 is carried out stochastically along the whole microtubule length, rather than from the open extremities. Our data thus complement prior studies on tubulin acetylation and further strengthen the rationale for the correlation between tubulin acetylation and microtubule age.