The helical structure of double-stranded DNA is destabilized by increasing temperature. Above a critical temperature (the melting temperature), the two strands in duplex DNA become fully separated. Below this temperature, the structural effects are localized. Using tethered particle motion in a temperature-controlled sample chamber, we systematically investigated the effect of increasing temperature on DNA structure and the interplay between this effect and protein binding. Our measurements revealed that (1) increasing temperature enhances DNA flexibility, effectively leading to more compact folding of the double-stranded DNA chain, and (2) temperature differentially affects different types of DNA-bending chromatin proteins from mesophilic and thermophilic organisms. Thus, our findings aid in understanding genome organization in organisms thriving at moderate as well as extreme temperatures. Moreover, our results underscore the importance of carefully controlling and measuring temperature in single-molecule DNA (micromanipulation) experiments.