Novel traits play a key role in evolution, but their origins remain poorly understood. Here we address this problem by using experimental evolution to study bacterial innovation in real time. We allowed 380 populations of Pseudomonas aeruginosa to adapt to 95 different carbon sources that challenged bacteria with either evolving novel metabolic traits or optimizing existing traits. Whole genome sequencing of more than 80 clones revealed profound differences in the genetic basis of innovation and optimization. Innovation was associated with the rapid acquisition of mutations in genes involved in transcription and metabolism. Mutations in pre-existing duplicate genes in the P. aeruginosa genome were common during innovation, but not optimization. These duplicate genes may have been acquired by P. aeruginosa due to either spontaneous gene amplification or horizontal gene transfer. High throughput phenotype assays revealed that novelty was associated with increased pleiotropic costs that are likely to constrain innovation. However, mutations in duplicate genes with close homologs in the P. aeruginosa genome were associated with low pleiotropic costs compared to mutations in duplicate genes with distant homologs in the P. aeruginosa genome, suggesting that functional redundancy between duplicates facilitates innovation by buffering pleiotropic costs.