Living cells compartmentalize materials and enzymatic reactions to increase metabolic efficiency. While eukaryotes use membrane-bound organelles, bacteria and archaea rely primarily on protein-bound nanocompartments. Encapsulins constitute a class of nanocompartments widespread in bacteria and archaea whose functions have hitherto been unclear. Here, we characterize the encapsulin nanocompartment from Myxococcus xanthus, which consists of a shell protein (EncA, 32.5 kDa) and three internal proteins (EncB, 17 kDa; EncC, 13 kDa; EncD, 11 kDa). Using cryo-electron microscopy, we determined that EncA self-assembles into an icosahedral shell 32 nm in diameter (26 nm internal diameter), built from 180 subunits with the fold first observed in bacteriophage HK97 capsid. The internal proteins, of which EncB and EncC have ferritin-like domains, attach to its inner surface. Native nanocompartments have dense iron-rich cores. Functionally, they resemble ferritins, cage-like iron storage proteins, but with a massively greater capacity (similar to 30,000 iron atoms versus similar to 3,000 in ferritin). Physiological data reveal that few nanocompartments are assembled during vegetative growth, but they increase fivefold upon starvation, protecting cells from oxidative stress through iron sequestration.