In this study, we experimentally characterize an entire ancestral tree (1158 sequences) of the Lac repressor by pooled screening to reveal the evolutionary landscape of DNA specificity for the E. coli Lac operator. We find dozens of members across the ancestral tree that can function as repressors of the E. coli lac operator. These functional variants contain as many as 35 mutations (in the 60-residue DBD) in the DNA-binding domain as compared to extant E. coli lac repressor. These sequences belong to three distinct phylogenetic clusters indicating a highly rugged evolutionary landscape. While the shallower nodes (recent) are functional, the deeper nodes (ancient) are not. This suggests that unless genes are conserved by purifying selection, mutation and drift erode ancestral sequences resulting in loss of function. The local evolutionary landscape within a cluster shows a gain or loss of function between adjacent nodes indicating rapid rewiring of repressor-operator complexes which may be beneficial for the development of orthogonal genetic regulation. We carried out deep mutational scanning of the extant LacI DBD and compared its profile to ancestral amino acid preferences to discover the selective pressure on individual amino acids of the DBD and the residues potentiated to achieve new specificity. In vitro binding assays with molecular dynamics and protein evolution simulations reveal that rapid rewiring of specificity arises due to the necessity for regulators to simultaneously evolve specificity for either DNA half-site in asymmetric operators. In summary, our study provides fundamental insights into nature’s design of genetic regulation, evolutionary rules of protein-DNA recognition, and the biophysical mechanism of TF allostery.