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 describe 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 to 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 is highly cooperative and suggests that CmpA co-transports bicarbonate and calcium.