Anthropogenic CO2 emissions are projected to lower the pH of the ocean 0.3 units by 2100. Previous studies suggested that Prochlorococcus and Synechococcus, the numerically dominant phytoplankton in the oceans, have different responses to elevated CO2 that may result in a dramatic shift in their relative abundances in future oceans. Here we showed that the exponential growth rates of these two genera respond to future CO2 conditions in a manner similar to other cyanobacteria, but Prochlorococcus strains had significantly lower realized growth rates under elevated CO2 regimes due to poor survival after exposure to fresh culture media. Despite this, a Synechococcus strain was unable to outcompete a Prochlorococcus strain in co-culture at elevated CO2. Under these conditions, Prochlorococcus' poor response to elevated CO2 disappeared, and Prochlorococcus' relative fitness showed negative frequency dependence, with both competitors having significant fitness advantages when initially rare. These experiments suggested that the two strains should be able to coexist indefinitely in co-culture despite sharing nearly identical nutritional requirements. We speculate that negative frequency dependence exists due to reductive Black Queen evolution that has resulted in a passively mutualistic relationship analogous to that connecting Prochlorococcus with the ‘helper’ heterotrophic microbes in its environment.