Microtubules (MTs) are essential components of the eukaryotic cytoskeleton that serve as “highways” for intracellular trafficking. In addition to the well-known active transport of cargo by motor proteins, many MT-binding proteins seem to adopt diffusional motility as a transportation mechanism. However, because of the limited spatial resolution of current experimental techniques, the detailed mechanism of protein diffusion has not been elucidated. In particular, the precise role of tubulin tails and tail modifications in the diffusion process is unclear. Here, using coarsegrained molecular dynamics simulations validated against atomistic simulations, we explore the molecular mechanism of protein diffusion along MTs. We found that electrostatic interactions play a central role in protein diffusion; the disordered tubulin tails enhance affinity but slow down diffusion, and diffusion occurs in discrete steps. While diffusion along wild-type MT is performed in steps of dimeric tubulin, the removal of the tails results in a step of monomeric tubulin. We found that the energy barrier for diffusion is larger when diffusion on MTs is mediated primarily by the MT tails rather than the MT body. In addition, globular proteins (EB1 and PRC1) diffuse more slowly than an intrinsically disordered protein (Tau) on MTs. Finally, we found that polyglutamylation and polyglycylation of tubulin tails lead to slower protein diffusion along MTs, although polyglycylation leads to faster diffusion across MT protofilaments. Taken together, our results explain experimentally observed data and shed light on the roles played by disordered tubulin tails and tail modifications in the molecular mechanism of protein diffusion along MTs.