Frequent fluctuations in sulfate availability rendered syntrophic interactions between the sulfate reducing bacterium Desulfovibrio vulgaris (Dv) and the methanogenic archaeon Methanococcus maripaludis (Mm) unsustainable. By contrast, prolonged laboratory evolution in obligate syntrophy conditions improved the productivity of this community but at the expense of erosion of sulfate respiration (SR). Hence, we sought to understand the evolutionary trajectories that could both increase the productivity of syntrophic interactions and sustain SR. We combined a temporal and combinatorial survey of mutations accumulated over 1000 generations of 9 independently-evolved communities with analysis of the genotypic structure for one community down to the single-cell level. We discovered a high level of parallelism across communities despite considerable variance in their evolutionary trajectories and the perseverance of a rare SR+ Dv lineage within many evolution lines. An in-depth investigation revealed that synergistic epistasis across Dv and Mm genotypes had enhanced cooperativity within SR- and SR+ assemblages, allowing their co-existence as r- and K-strategists, respectively.