The carboxysome is a bacterial organelle found in all cyanobacteria; it encapsulates CO2 fixation enzymes within a protein shell. The most abundant carboxysome shell protein contains a single bacterial microcompartment (BMC) domain. We present in vivo evidence that a hypothetical protein (dubbed CcmP) encoded in all beta-cyanobacterial genomes is part of the carboxysome. We show that CcmP is a tandem BMC domain protein, the first to be structurally characterized from a beta-carboxysome. CcmP forms a dimer of tightly stacked trimers, resulting in a nanocompartment-containing shell protein that may weakly bind 3-phosphoglycerate, the product of CO2 fixation. The trimers have a large central pore through which metabolites presumably pass into the carboxysome. Conserved residues surrounding the pore have alternate side-chain conformations suggesting that it can be open or closed. Furthermore, CcmP and its orthologs in alpha-cyanobacterial genomes form a distinct clade of shell proteins. Members of this subgroup are also found in numerous heterotrophic BMC-associated gene clusters encoding functionally diverse bacterial organelles, suggesting that the potential to form a nanocompartment within a microcompartment shell is widespread. Given that carboxysomes and architecturally related bacterial organelles are the subject of intense interest for applications in synthetic biology/metabolic engineering, our results describe a new type of building block with which to functionalize BMC shells.