The mobility of protein is fundamental in the machinery of life. Here, we have investigated the effect of DNA binding in conjunction with DNA segmental fluctuation (internal motion) of the bacterial Hfq master regulator devoid of its amyloid C-terminus domain. Hfq is one of the most abundant nucleoid associated proteins that shape the bacterial chromosome and is involved in several aspects of nucleic acid metabolism. Fluorescence microscopy has been used to track a C-terminus domain lacking mutant form of Hfq on double-stranded DNA, which is stretched by confinement to a rectangular nanofluidic channel. The mobility of the mutant is strongly accelerated with respect to the wild-type variant. Furthermore, it shows a reverse dependence on the internal motion of DNA, in that slower motion results in slower protein diffusion. The results demonstrate the subtle role of DNA internal motion in controlling the mobility of a nucleoid associated protein, and, in particular, the importance of transient binding and moving DNA strands out of the way.