Metals can play key roles in stabilizing protein structures, but ensuring their proper incorporation is a challenge when a metalloprotein is overexpressed in a non-native cellular environment. Here, we have used computational protein design tools to redesign cytochrome b562 (cyt b562), which relies on the binding of its heme cofactor to achieve its proper fold, into a stable, heme-free protein. The resulting protein, ApoCyt, features only four mutations and no metal-ligand or covalent bonds, yet displays improved stability over cyt b562. Mutagenesis studies and X-ray crystal structures reveal that the increase in stability is due to the computationally prescribed mutations, which stabilize the protein fold through a combination of hydrophobic packing interactions, hydrogen bonds, and cation-π interactions. Upon installation of the relevant mutations, ApoCyt is capable of assembling into previously reported, cytochrome-based trimeric and tetrameric assemblies, demonstrating that ApoCyt retains the structure and assembly properties of cyt b562. The successful design of ApoCyt therefore enables further functional diversification of cytochrome-based assemblies and demonstrates that structural metal cofactors can be replaced by a small number of well-designed, non-covalent interactions.