Adaptation under similar selective pressure often leads to comparable phenotypes. A longstanding question is whether such phenotypic repeatability entails similar (parallelism) or different genotypic changes (convergence). To better understand this, we characterized mutations that optimized expression of a plasmid-borne metabolic pathway during laboratory evolution of a bacterium. Expressing these pathway genes was essential for growth but came with substantial costs. Starting from overexpression, replicate populations founded by this bacterium all evolved to reduce expression. Despite this phenotypic repetitiveness, the underlying mutational spectrum was highly diverse. Analysis of these plasmid mutations identified three distinct means to modulate gene expression: (1) reducing the gene copy number, (2) lowering transcript stability, and (3) integration of the pathway-bearing plasmid into the host genome. Our study revealed diverse molecular changes beneath convergence to a simple phenotype. This complex genotype-phenotype mapping presents a challenge to inferring genetic evolution based solely on phenotypic changes.