Nucleotide excision repair (NER) is an evolutionarily conserved mechanism that processes helix-destabilizing and/or -distorting DNA lesions, such as UV-induced photoproducts. Here, we investigate the dynamic protein-DNA interactions during the damage recognition step using single-molecule fluorescence microscopy. Quantum dot-labeled Rad4-Rad23 (yeast XPC-RAD23B ortholog) forms non-motile complexes or conducts a one-dimensional search via either random diffusion or constrained motion. Atomic force microcopy analysis of Rad4 with the β-hairpin domain 3 (BHD3) deleted reveals that this motif is non-essential for damage-specific binding and DNA bending. Furthermore, we find that deletion of seven residues in the tip of β-hairpin in BHD3 increases Rad4-Rad23 constrained motion at the expense of stable binding at sites of DNA lesions, without diminishing cellular UV resistance or photoproduct repair in vivo. These results suggest a distinct intermediate in the damage recognition process during NER, allowing dynamic DNA damage detection at a distance.