Metal coordination is a key structural and functional component of a large fraction of proteins. Given this dual role we considered the possibility that metal coordination may have played a templating role in the early evolution of protein folds and complexes. We describe here a rational design approach, Metal Templated Interface Redesign (MeTIR), that mimics the time course of a hypothetical evolutionary pathway for the formation of stable protein assemblies through an initial metal coordination event. Using a folded monomeric protein, cytochrome cb(562), as a building block we show that its non-self-associating surface can be made self-associating through a minimal number of mutations that enable Zn coordination. The protein interfaces in the resulting Zn-directed, D(2)-symmetrical tetramer are subsequently redesigned, yielding unique protein architectures that self-assemble in the presence or absence of metals. Aside from its evolutionary implications, MeTIR provides a route to engineer de novo protein interfaces and metal coordination environments that can be tuned through the extensive noncovalent bonding interactions in these interfaces.