The generation of complex morphological features requires the precisely orchestrated expression of numerous genes during development. While several traits have been resolved to evolutionary changes within a single gene, the evolutionary path by which genes derive co-localized or mutually excluded expression patterns is currently a mystery. Here we investigate how the Drosophila pigmentation gene network was altered in Drosophila prostipennis, a species in the Drosophila melanogaster subgroup, that evolved expanded abdominal pigmentation. We show that this expansion involved broadened expression of the melanin-promoting enzyme genes tan and yellow, and a reciprocal withdrawn pattern of the melanin-suppressing enzyme gene ebony. To examine whether these coordinated changes to the network were generated through mutations in the cis-regulatory elements (CREs) of these genes, we cloned and tested CREs of D. prostipennis tan, ebony, and yellow in transgenic reporter assays. Regulatory regions of both tan and ebony failed to recapitulate the derived D. prostipennis expression phenotype, implicating the modification of a factor or factors upstream of both genes. However, the D. prostipennis yellow cis-regulatory region recapitulated the expanded expression pattern observed in this species, implicating causative mutations in cis to yellow. Our results provide an example in which a coordinated expression program evolved through independent changes at multiple loci, rather than through changes to a single “master regulator” directing a suite of downstream target genes. This implies a complex network structure in which each gene may be subject to a unique set of inputs, and resultantly may require individualized evolutionary paths to yield correlated gene expression patterns.