Cellular gene expression programs are encoded in the DNA by regulatory sequences – each containing multiple short motifs where transcription factors bind. Despite extensive characterization of the relevant molecular machinery, much remains unknown about the evolution of this regulatory system. Using simulations and information-theoretic arguments we study the evolutionary dynamics of entire regulatory sequences in a simple biophysically-inspired model of metazoan gene regulation. We hypothesize that evolution, over the long run, adjusted the properties of the regulatory machinery to balance selection for binding cognate motifs with selection against binding noncognate ones. This balance defines an optimal regime where regulatory sequences are most evolvable, providing a substrate for rapid phenotypic adaptation and explaining a number of perplexing observations about the organization of gene regulation in prokaryotes and eukaryotes.