Architectural DNA-binding proteins (ADBPs) are abundant constituents of eukaryotic or bacterial chromosomes that bind DNA promiscuously and function in diverse DNA reactions. They generate large conformational changes in DNA upon binding yet can slide along DNA when searching for functional binding sites. Here we investigate the mechanism by which ADBPs diffuse on DNA by single-molecule analyses of mutant proteins rationally chosen to distinguish between rotation-coupled diffusion and DNA surface sliding after transient unbinding from the groove(s). The properties of yeast Nhp6A mutant proteins, combined with molecular dynamics simulations, suggest Nhp6A switches between two binding modes: a static state, in which the HMGB domain is bound within the minor groove with the DNA highly bent, and a mobile state, where the protein is traveling along the DNA surface by means of its flexible N-terminal basic arm. The behaviors of Fis mutants, a bacterial nucleoid-associated helix-turn-helix dimer, are best explained by mobile proteins unbinding from the major groove and diffusing along the DNA surface. Nhp6A, Fis, and bacterial HU are all near exclusively associated with the chromosome, as packaged within the bacterial nucleoid, and can be modeled by three diffusion modes where HU exhibits the fastest and Fis the slowest diffusion.