Mutualisms, or interactions between species where both provide a net fitness benefit to each other, are numerous and ecologically relevant. Presumably, these interactions affect the evolution of both species, possibly resulting in coevolution where evolutionary changes in one causes selection for changes in the other species. However, rigorous studies of coevolution in mutualisms have been uncommon, have often focused on only one of the species involved, have focused on highly-evolved mutualisms, and rarely on microorganisms. In this presentation, I will describe our attempts to test whether or not coevolution is a common feature of evolution in the first 5000 generations of adaptation to a new mutualism. The mutualism we studied is composed of the sulfate-reducing bacteria Desulfovibrio vulgaris, and the archaeon Methanococcus maripaludis. These species were put in an environment where there was no sulfate, and the only means for survival for both species is to cooperatively ferment lactate, passing electrons via hydrogen to provide energy to M. maripaludis and maintain favorable growth conditions for D. vulgaris. Similar species and interactions play a fundamental role in carbon degradation and methane production in environments such as rice paddies, cow rumens, and anaerobic digestors. In addition, efficient transfer of hydrogen between the species is in the best interest of both parties, suggesting few, if any opportunities for cheating. We tested whether these species have coevolved using timeshift experiments, where the fitness of a population with partners from its past and future is compared. In addition, we have sequenced the metagenomes of many of these communities over time, and the prevalence of evolutionary dynamics resembling expected coevolution will be discussed.