Dive capacities of air-breathing vertebrates are dictated by onboard O stores, suggesting that physiologic specialization of diving birds such as penguins may have involved adaptive changes in convective O transport. It has been hypothesized that increased hemoglobin (Hb)-O affinity improves pulmonary O extraction and enhances the capacity for breath-hold diving. To investigate evolved changes in Hb function associated with the aquatic specialization of penguins, we integrated comparative measurements of whole-blood and purified native Hb with protein engineering experiments based on site-directed mutagenesis. We reconstructed and resurrected ancestral Hb representing the common ancestor of penguins and the more ancient ancestor shared by penguins and their closest nondiving relatives (order Procellariiformes, which includes albatrosses, shearwaters, petrels, and storm petrels). These two ancestors bracket the phylogenetic interval in which penguin-specific changes in Hb function would have evolved. The experiments revealed that penguins evolved a derived increase in Hb-O affinity and a greatly augmented Bohr effect (i.e., reduced Hb-O affinity at low pH). Although an increased Hb-O affinity reduces the gradient for O diffusion from systemic capillaries to metabolizing cells, this can be compensated by a concomitant enhancement of the Bohr effect, thereby promoting O unloading in acidified tissues. We suggest that the evolved increase in Hb-O affinity in combination with the augmented Bohr effect maximizes both O extraction from the lungs and O unloading from the blood, allowing penguins to fully utilize their onboard O stores and maximize underwater foraging time.