Single-stranded DNA generated in the cell during DNA metabolism is stabilized and protected by binding of ssDNA-binding (SSB) proteins. Escherichia coli SSB, a representative homotetrameric SSB, binds to ssDNA by wrapping the DNA using its four subunits. However, such a tightly wrapped, high-affinity protein-DNA complex still needs to be removed or repositioned quickly for unhindered action of other proteins. Here we show, using single-molecule two- and three-colour fluorescence resonance energy transfer, that tetrameric SSB can spontaneously migrate along ssDNA. Diffusional migration of SSB helps in the local displacement of SSB by an elongating RecA filament. SSB diffusion also melts short DNA hairpins transiently and stimulates RecA filament elongation on DNA with secondary structure. This observation of diffusional movement of a protein on ssDNA introduces a new model for how an SSB protein can be redistributed, while remaining tightly bound to ssDNA during recombination and repair processes.