Carboxysomes are bacterial microcompartments that enhance carbon fixation by concentrating ribulose-1,5-bisphosphate carboxylase/oxygenase (RuBisCO) and its substrate CO2 within a proteinaceous shell. They are found in all cyanobacteria, some purple photoautotrophs and many chemoautotrophic bacteria. Carboxysomes consist of a protein shell that encapsulates several hundred molecules of RuBisCO, and contain carbonic anhydrase and other accessory proteins. Genes coding for carboxysome shell components and the encapsulated proteins are typically found together in an operon. The α-carboxysome operon is embedded in a cluster of additional, conserved genes that are presumably related to its function. In many chemoautotrophs, products of the expanded carboxysome locus include CbbO and CbbQ, a member of the AAA+ domain superfamily. We bioinformatically identified subtypes of CbbQ proteins and show that their genes frequently co-occur with both Form IA and Form II RuBisCO. The α-carboxysome-associated ortholog, CsoCbbQ, from Halothiobacillus neapolitanus forms a hexamer in solution and hydrolyzes ATP. The crystal structure shows that CsoCbbQ is a hexamer of the typical AAA+ domain; the additional C-terminal domain, diagnostic of the CbbQ subfamily, structurally fills the inter-monomer gaps, resulting in a distinctly hexagonal shape. We show that CsoCbbQ interacts with CsoCbbO and is a component of the carboxysome shell, the first example of ATPase activity associated with a bacterial microcompartment.