Microbial communities are comprised of many species that coexist on small spatial scales. This is difficult to explain because many interspecies interactions are competitive, and ecological theory predicts that one species will drive the extinction of another species that competes for the same resource. Conversely, evolutionary theory proposes that natural selection can lead to coexistence by driving competing species to use non-overlapping resources. However, evolutionary escape from extinction may be slow compared to the rate of competitive exclusion. Here, we use experimental co-cultures of Escherichia coli and Saccharomyces cerevisiae to study the evolution of coexistence in species that compete for resources. We find that while E. coli usually outcompetes S. cerevisiae in co-culture, a few populations evolved stable coexistence after ~1000 generations of coevolution. We sequenced S. cerevisiae and E. coli populations, identified multi-hit genes, and engineered alleles from these genes into several genetic backgrounds, finding that some mutations modified interactions between E. coli and S. cerevisiae. Together, our data demonstrate that coexistence can evolve, de novo, from intense competition between two species with no history of coevolution.