Interaction of regulatory DNA binding proteins with their target sites is usually preceded by binding to nonspecific DNA. This speeds up the search for the target site by several orders of magnitude. We report the solution structure and dynamics of the complex of a dimeric lac repressor DNA binding domain with nonspecific DNA. The same set of residues can switch roles from a purely electrostatic interaction with the DNA backbone in the nonspecific complex to a highly specific binding mode with the base pairs of the cognate operator sequence. The protein-DNA interface of the nonspecific complex is flexible on biologically relevant time scales that may assist in the rapid and efficient finding of the target site.