Evolutionary novelties have been important in the history of life, but their origins are usually difficult to examine in detail. We previously described the evolution of a novel trait, aerobic citrate utilization (Cit+), in an experimental population of Escherichia coli. Here we analyze 29 genomes to investigate the history and genetic basis of this trait. At least three distinct clades coexisted for more than 10,000 generations prior to its emergence. The Cit+ trait originated in one clade by a tandem duplication that captured an aerobically-expressed promoter for the expression of a previously silent citrate transporter. The clades varied in their propensity to evolve this novel trait, although genotypes able to do so existed in all three clades, implying that multiple potentiating mutations arose during the population’s history. Our findings illustrate the importance of promoter capture and altered gene regulation in mediating the exaptation events that often underlie evolutionary innovations.