Mutualisms are essential for life, yet it is unclear how they arise. A two-stage process has been proposed for the evolution of mutualisms that involve exchanges of two costly resources. First, costly provisioning by one species may be selected for if that species gains a benefit from costless byproducts generated by a second species, and cooperators get disproportionate access to byproducts. Selection could then drive the second species to provide costly resources in return. Previously, a synthetic consortium evolved the first stage of this scenario: Salmonella enterica evolved costly production of methionine in exchange for costless carbon byproducts generated by an auxotrophic Escherichia coli. Growth on agar plates localized the benefits of cooperation around methionine-secreting S. enterica. Here, we report that further evolution of these partners on plates led to hypercooperative E. coli that secrete the sugar galactose. Sugar secretion arose repeatedly across replicate communities and is costly to E. coli producers, but enhances the growth of S. enterica. The tradeoff between individual costs and group benefits led to maintenance of both cooperative and efficient E. coli genotypes in this spatially structured environment. This study provides an experimental example of de novo, bidirectional costly mutualism evolving from byproduct consumption. The results validate the plausibility of costly cooperation emerging from initially costless exchange, a scenario widely used to explain the origin of the mutualistic species interactions that are central to life on Earth.