Frequently during evolution, new phenotypes evolved due to novelty in gene regulation, such as that caused by genome rewiring. This has been demonstrated by comparing common regulatory sequences among species and by identifying single regulatory mutations that are associated with new phenotypes. However, while a single mutation changes a single element, gene regulation is accomplished by a regulatory network involving multiple interactive elements. Therefore, to better understand regulatory evolution, we have studied how mutations contributed to the adaptation of cells to a regulatory challenge. We created a synthetic genome rewiring in yeast cells, challenged their gene regulation, and studied their adaptation. HIS3, an essential enzyme for histidine biosynthesis, was placed exclusively under a GAL promoter, which is induced by galactose and strongly repressed in glucose. Such rewired cells were faced with significant regulatory challenges in a repressive glucose medium. We identified several independent mutations in elements of the GAL system associated with the rapid adaptation of cells, such as the repressor GAL80 and the binding sites of the activator GAL4. Consistent with the extraordinarily high rate of cell adaptation, new regulation emerged during adaptation via multiple trajectories, including those involving mutations in elements of the GAL system. The new regulation of HIS3 tuned its expression according to histidine requirements with or without these significant mutations, indicating that additional factors participated in this regulation and that the regulatory network could reorganize in multiple ways to accommodate different mutations. This study, therefore, stresses network plasticity as an important property for regulatory adaptation and evolution.