DNA-binding transcriptional regulators control gene expression and are among the most complex and powerful proteins in nature. They have been studied extensively as model systems for a variety of biochemical and biophysical phenomena and are valuable tools for regulating synthetic gene networks and metabolic pathways. Despite recent interest, the rational design of novel transcriptional regulators for use in biotechnology has remained elusive due to the challenges of computational protein design. The study of molecular evolution can provide insight on the emergence of complex biophysical properties by emphasising sequence-function relationships and can aid in guiding protein engineering efforts. Here, we investigate the biophysical properties that underpin DNA recognition in the LacI/GalR Family of bacterial transcriptional regulators. We performed comprehensive phylogenetic analyses and ancestral sequence reconstruction to generate a library of 1161 protein sequences that represent the full diversity and evolutionary history of the LacI/GalR Family. By assaying this evolutionarily informed library with fluorescence activated cell sorting, we identified a pool of sequences capable of binding a specific DNA operator sequence. Surprisingly, proteins capable of repression were only distantly related to one another and recognition of specific DNA sequences appears to be acquired and lost stochastically and rapidly in very few mutations, providing novel insight on the biophysical mechanisms of DNA recognition and the molecular evolution of DNA-binding transcriptional regulators.