Duplication of ancestral hypoxia-inducible factor (HIF)α coincided with the evolution of vertebrate species. Paralogs HIF1α and HIF2α are the most well-known factors for modulating the cellular transcriptional profile following hypoxia. However, how the processes of natural selection acted upon the coding region of these two genes to optimize the cellular response to hypoxia during evolution remains unclear. A key negative regulator of HIFα is von Hippel-Lindau (VHL) tumour suppressor protein. Here we show that evolutionarily-relevant substitutions can modulate a secondary contact between HIF1α Met561 and VHL Phe91. Notably, HIF1α binds more tightly than HIF2α to VHL due to a conserved Met to Thr substitution observed in the vertebrate lineage. Similarly, substitution of VHL Phe91 with Tyr, as seen in invertebrate species, decreases VHL affinity for both HIF1α and HIF2α. We propose that vertebrate evolution involved a more complex hypoxia response with fine-tuned divergence of VHL affinity for HIF1α and HIF2α.