It has been proposed that certain type II restriction enzymes (REs), such as EcoRV, track the helical pitch of DNA as they diffuse along DNA, a so-called rotation-coupled sliding. As of yet, there is no direct experimental observation of this phenomenon, but mounting indirect evidence gained from single-molecule imaging of RE-DNA complexes support the hypothesis. We address this issue by conjugating fluorescent labels of varying size (organic dyes, proteins and quantum dots) to EcoRV, and by fusing it to the engineered Rop protein scRM6. Single-molecule imaging of these modified EcoRVs sliding along DNA provides us with their linear diffusion constant (D(1)), revealing a significant size dependency. To account for the dependence of D(1) on the size of the EcoRV label, we have developed four theoretical models describing different types of motion along DNA and find that our experimental results are best described by rotation-coupled sliding of the protein. The similarity of EcoRV to other type II REs and DNA binding proteins suggests that this type of motion could be widely preserved in other biological contexts.