Ecological opportunities promote population divergence into coexisting lineages. However, the genetic mechanisms that enable new lineages to exploit these opportunities are poorly understood except in cases of single mutations. We examined how two Escherichia coli lineages diverged from their common ancestor at the outset of a long-term coexistence. By sequencing genomes and reconstructing the genetic history of one lineage, we showed that three mutations together were sufficient to produce the frequency-dependent fitness effects that allowed this lineage to invade and stably coexist with the other. These mutations all affected regulatory genes and collectively caused substantial metabolic changes. Moreover, the particular derived alleles were critical for the initial divergence and invasion, indicating that the establishment of this polymorphism depended on specific epistatic interactions.