Autotrophic bacteria rely on various mechanisms to increase intracellular concentrations of inorganic forms of carbon (i.e., bicarbonate and CO2) in order to improve the efficiency with which they can be converted to organic forms. Transmembrane bicarbonate transporters and carboxysomes play key roles in accumulating bicarbonate and CO2, but other regulatory elements of carbon concentration mechanisms in bacteria are less understood. In this study, after analyzing the genomic regions around α-type carboxysome operons, we characterize a protein that is conserved across these operons but has not been previously studied. On the basis of a series of apo- and ligand-bound crystal structures and supporting biochemical data, we show that this protein, which we refer to as the carboxysome-associated PII protein (CPII), represents a new and distinct subfamily within the broad superfamily of previously studied PII regulatory proteins, which are generally involved in regulating nitrogen metabolism in bacteria. CPII undergoes dramatic conformational changes in response to ADP binding, and the affinity for nucleotide binding is strongly enhanced by the presence of bicarbonate. CPII therefore appears to be a unique type of PII protein that senses bicarbonate availability, consistent with its apparent genomic association with the carboxysome and its constituents.