Most proteins associate into multimeric complexes with specific architectures1,2, which often have functional properties such as cooperative ligand binding or allosteric regulation3. No detailed knowledge is available about how any multimer and its functions arose during evolution. Here we use ancestral protein reconstruction and biophysical assays to elucidate the origins of vertebrate haemoglobin, a heterotetramer of paralogous α- and β-subunits that mediates respiratory oxygen transport and exchange by cooperatively binding oxygen with moderate affinity. We show that modern haemoglobin evolved from an ancient monomer and characterize the historical 'missing link' through which the modern tetramer evolved-a noncooperative homodimer with high oxygen affinity that 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 favourable contacts with more ancient residues on the opposing subunit. These surface substitutions markedly reduce oxygen affinity and even confer cooperativity, because an ancient linkage between the oxygen binding site and the multimerization interface was already an intrinsic feature of the protein's structure. Our findings establish that evolution can produce new complex molecular structures and functions via simple genetic mechanisms that recruit existing biophysical features into higher-level architectures.