Cyanobacteria, blue-green algae, are the most abundant autotrophs in aquatic environments and form the base of the food chain by fixing carbon and nitrogen into cellular biomass. To compensate for the low selectivity of Rubisco for CO2 over O2, cyanobacteria have developed highly efficient CO2-concentrating machinery of which the ABC transport system CmpABCD from Synechocystis PCC 6803 is one component. Here, we have described the structure of the bicarbonate-binding protein CmpA in the absence and presence of bicarbonate and carbonic acid. CmpA is highly homologous to the nitrate transport protein NrtA. CmpA binds carbonic acid at the entrance to the ligand-binding pocket, whereas bicarbonate binds in nearly an identical location compared with nitrate binding to NrtA. Unexpectedly, bicarbonate binding is accompanied by a metal ion, identified as Ca2+ via inductively coupled plasma optical emission spectrometry. The binding of bicarbonate and metal appears to be highly cooperative and suggests that CmpA may co-transport bicarbonate and calcium or that calcium acts a cofactor in bicarbonate transport.