Predation is widespread in all ecosystems and is integral to many ecological and evolutionary processes including population dynamics, extinction rates and speciation. Beyond large eukaryotes, predation is also found among bacteria and may play a major role in shaping the composition and evolution of microbial communities. Among bacterial predators, Myxococcus xanthus preys upon a wide range of microbial species using a unique predation strategy based on the combination of several social behaviors. Experimental evolution is a powerful way to explore the evolution of bacterial interactions and to investigate the resulting genetic and phenotypic adaptations. We established an experimental co-evolution system with M. xanthus as predator and Escherichia coli as prey in which the prey grew on a carbon source (glucose) that the predators cannot utilize, such that they depend solely on prey consumption for survival. After ~200 prey-generations of evolution we found evidence of adaptation by both predators and prey, which exhibited fitness advantages over their ancestors and evolved controls. Such adaptation appears to be specific to the predator-prey interaction as the coevolved populations were not fitter compared to controls in the absence of their partner. Moreover, both prey and predators exhibited strong signatures of convergent genetic evolution. In E. coli, the gene coding for the protease ompT was mutated or deleted in all but one coevolved populations and in none of the control populations that evolved in the absence of predators. Deletion of ompT in the prey ancestor resulted in a fitness advantage only in the presence of predators. Reciprocally, in M. xanthus, the uncharacterized gene Mxan_5760 was mutated or deleted in all coevolved populations but not in control populations. These experiments highlight the importance of predatory interactions in microbial evolution and open opportunities for more complex experimental studies of microbial food-web evolution at multiple trophic levels.