Most proteins associate into multimeric complexes with specific architectures, which often have functional properties like cooperative ligand binding or allosteric regulation. No detailed knowledge is available about how any multimer and its functions arose during historical evolution. Here we use ancestral protein reconstruction and biophysical assays to dissect the origins of vertebrate hemoglobin (Hb), a heterotetramer of paralogous α and β subunits, which mediates respiratory oxygen transport and exchange by cooperatively binding oxygen with moderate affinity. We show that modern Hb evolved from an ancient monomer and characterize the historical “missing-link” through which the modern tetramer evolved–a noncooperative homodimer with high oxygen affinity, which existed before the gene duplication that generated distinct α and β subunits. Reintroducing just two post-duplication historical substitutions into the ancestral protein is sufficient to cause strong tetramerization by creating favorable contacts with more ancient residues on the opposing subunit. These surface substitutions dramatically reduce oxygen affinity and even confer weak cooperativity, because of an ancient structural linkage between the oxygen binding site and the multimerization interface. Our findings establish that evolution can produce new complex molecular structures and functions via simple genetic mechanisms, which recruit existing biophysical features into higher-level architectures.