In diving birds like penguins, physiologic considerations suggest that increased hemoglobin (Hb)-O2 affinity may improve pulmonary O2 extraction and enhance dive capacity. We integrated experimental tests on whole-blood and native Hbs of penguins with protein engineering experiments on reconstructed ancestral Hbs. The experiments involving ancestral protein resurrection enabled us to test for evolved changes in Hb function in the stem lineage of penguins after divergence from their closest nondiving relatives. We demonstrate that penguins evolved an increased Hb-O2 affinity in conjunction with a greatly augmented Bohr effect (i.e., reduction in Hb-O2 affinity at low pH) that should maximize pulmonary O2 extraction without compromising O2 delivery at systemic capillaries.