Bacterial microcompartments are primitive organelles composed entirely of protein subunits. Genomic sequence databases reveal the widespread occurrence of microcompartments across diverse microbes. The prototypical bacterial microcompartment is the carboxysome, a protein shell for sequestering carbon fixation reactions. We report three-dimensional crystal structures of multiple carboxysome shell proteins, revealing a hexameric unit as the basic microcompartment building block and showing how these hexamers assemble to form flat facets of the polyhedral shell. The structures suggest how molecular transport across the shell may be controlled and how structural variations might govern the assembly and architecture of these subcellular compartments.