Evolution of gene regulation is an important contributor to the variety of life. Here, we analyse the evolution of a combinatorial transcriptional circuit composed of sequence-specific DNA-binding proteins that are conserved among all eukaryotes. This circuit regulates mating in the ascomycete yeast lineage. We first identify a group of mating genes that was transcriptionally regulated by an activator in a fungal ancestor, but is now transcriptionally regulated by a repressor in modern bakers' yeast. Despite this change in regulatory mechanism, the logical output of the overall circuit remains the same. By examining the regulation of mating in modern yeasts that are related to different extents, we deduce specific, sequential changes in both cis- and trans-regulatory elements that constitute the transition from positive to negative regulation. These changes indicate specific mechanisms by which fitness barriers were traversed during the transition.