Single-molecule approaches permit an unrivalled view of how complex systems operate and have recently been used to understand DNA–protein interactions. These tools have enabled advances in a particularly challenging problem, the search for damaged sites on DNA. DNA repair proteins are present at the level of just a few hundred copies in bacterial cells to just a few thousand in human cells, and they scan the entire genome in search of their specific substrates. How do these proteins achieve this herculean task when their targets may differ from undamaged DNA by only a single hydrogen bond? Here we examine, using single-molecule approaches, how the prokaryotic nucleotide excision repair system balances the necessity for speed against specificity. We discuss issues at a theoretical, biological, and technical level and finally pose questions for future research.