Polypeptides and polynucleotides are natural programmable biopolymers that can self-assemble into complex tertiary structures. We describe a system analogous to designed DNA nanostructures in which protein coiled-coil (CC) dimers serve as building blocks for modular de novo design of polyhedral protein cages that efficiently self-assemble in vitro and in vivo. We produced and characterized >20 single-chain protein cages in three shapes-tetrahedron, four-sided pyramid, and triangular prism-with the largest containing >700 amino-acid residues and measuring 11 nm in diameter. Their stability and folding kinetics were similar to those of natural proteins. Solution small-angle X-ray scattering (SAXS), electron microscopy (EM), and biophysical analysis confirmed agreement of the expressed structures with the designs. We also demonstrated self-assembly of a tetrahedral structure in bacteria, mammalian cells, and mice without evidence of inflammation. A semi-automated computational design platform and a toolbox of CC building modules are provided to enable the design of protein cages in any polyhedral shape.