Protein binding to DNA changes the DNA’s structure, and altered DNA structure can, in turn, modulate the dynamics of protein binding. This mutual dependency is poorly understood. Here we investigated dynamic couplings among protein binding to DNA, protein sliding on DNA, and DNA bending by applying a coarse-grained simulation method to the bacterial architectural protein HU and 14 other DNA-binding proteins. First, we verified our method by showing that the simulated HU exhibits a weak preference for A/T-rich regions of DNA and a much higher affinity for gapped and nicked DNA, consistent with biochemical experiments. The high affinity was attributed to a local DNA bend, but not the specific chemical moiety of the gap/nick. The long-time dynamic analysis revealed that HU sliding is associated with the movement of the local DNA bending site. Deciphering single sliding steps, we found the coupling between HU sliding and DNA bending is akin to neither induced-fit nor population-shift; instead they moved concomitantly. This is reminiscent of a cation transfer on DNA and can be viewed as a protein version of polaron-like sliding. Interestingly, on shorter time scales, HU paused when the DNA was highly bent at the bound position and escaped from pauses once the DNA spontaneously returned to a less bent structure. The HU sliding is largely regulated by DNA bending dynamics. With 14 other proteins, we explored the generality and versatility of the dynamic coupling and found that 6 of the 15 assayed proteins exhibit the polaron-like sliding.