Dynein is a motor protein that transports cellular cargo along the microtubule (MT) by consuming ATP. Dynein's microtubule-binding domain (MTBD) is separated from the ATP-binding core by a ~15 nm stalk that consists of two α-helices forming an antiparallel coiled coil. It was previously suggested that the coiled-coil stalk creates a registry shift to modulate its binding affinity for MT. A crystal structure of the low-affinity form of MTBD was determined, but that of the high-affinity form with the registry shift is not yet available. In this study, we obtained an all-atom model structure for the high-affinity form of MTBD bound to MT by an anisotropic network model, protein-protein docking, and molecular dynamics simulations. We observe that the magnitude of the coiled-coil helix sliding is dramatically reduced near the two prolines that form the stalk-MTBD boundary and subsequently transformed to cyclic movements of MTBD helices, leading to formation of a new salt bridge with MT at the binding interface. The proposed mechanism explains the roles of highly conserved residues such as the two prolines at the stalk-MTBD boundary, the nonpolar tryptophan and proline residues near the binding interface, and the electropositive residues forming salt bridges with MT.