Rising CO2 levels may act as an important selective factor on the CO2-concentrating mechanism (CCM) of cyanobacteria. We investigated genetic diversity in the CCM of Microcystis aeruginosa, a species producing harmful cyanobacterial blooms in many lakes worldwide. All 20 investigated Microcystis strains contained complete genes for two CO2 uptake systems, the ATP-dependent bicarbonate uptake system BCT1 and several carbonic anhydrases (CAs). However, 12 strains lacked either the high-flux bicarbonate transporter BicA or the high-affinity bicarbonate transporter SbtA. Both genes, bicA and sbtA, were located on the same operon, and the expression of this operon is most likely regulated by an additional LysR-type transcriptional regulator (CcmR2). Strains with only a small bicA fragment clustered together in the phylogenetic tree of sbtAB, and the bicA fragments were similar in strains isolated from different continents. This indicates that a common ancestor may first have lost most of its bicA gene and subsequently spread over the world. Growth experiments showed that strains with sbtA performed better at low inorganic carbon (Ci) conditions, whereas strains with bicA performed better at high Ci conditions. This offers an alternative explanation of previous competition experiments, as our results reveal that the competition at low CO2 levels was won by a specialist with only sbtA, whereas a generalist with both bicA and sbtA won at high CO2 levels. Hence, genetic and phenotypic variation in Ci uptake systems provide Microcystis with the potential for microevolutionary adaptation to changing CO2 conditions, with a selective advantage for bicA-containing strains in a high-CO2 world.