The carboxysome is a bacterial microcompartment that functions as a simple organelle by sequestering enzymes involved in carbon fixation. The carboxysome shell is roughly 800 to 1400 angstroms in diameter and is assembled from several thousand protein subunits. Previous studies have revealed the three-dimensional structures of hexameric carboxysome shell proteins, which self-assemble into molecular layers that most likely constitute the facets of the polyhedral shell. Here, we report the three-dimensional structures of two proteins of previously unknown function, CcmL and OrfA (or CsoS4A), from the two known classes of carboxysomes, at resolutions of 2.4 and 2.15 angstroms. Both proteins assemble to form pentameric structures whose size and shape are compatible with formation of vertices in an icosahedral shell. Combining these pentamers with the hexamers previously elucidated gives two plausible, preliminary atomic models for the carboxysome shell.