Although combinatorial regulation is a common feature in gene regulatory networks, how it evolves and affects network structure and function is not well understood. In S. cerevisiae, the phosphate starvation (PHO) responsive transcription factors Pho4 and Pho2 are required for gene induction and survival during phosphate starvation. In the related human commensal C. glabrata, Pho4 is required but Pho2 is dispensable for survival in phosphate starvation and is only partially required for inducing PHO genes. Phylogenetic survey suggests that reduced dependence on Pho2 evolved in C. glabrata and closely related species. In S. cerevisiae, less Pho2-dependent Pho4 orthologs induce more genes. In C. glabrata, its Pho4 binds to more locations and induces three times as many genes as Pho4 in S. cerevisiae does. Our work shows how evolution of combinatorial regulation allows for rapid expansion of a gene regulatory network’s targets, possibly extending its physiological functions.