The long-term accumulation of biodiversity has been punctuated by remarkable evolutionary transitions that allowed organisms to exploit new ecological opportunities. Mesozoic flying reptiles (the pterosaurs), which dominated the skies for more than 150 million years, were the product of one such transition. The ancestors of pterosaurs were small and probably bipedal early archosaurs1, which were certainly well-adapted to terrestrial locomotion. Pterosaurs diverged from dinosaur ancestors in the Early Triassic epoch (around 245 million years ago); however, the first fossils of pterosaurs are dated to 25 million years later, in the Late Triassic epoch. Therefore, in the absence of proto-pterosaur fossils, it is difficult to study how flight first evolved in this group. Here we describe the evolutionary dynamics of the adaptation of pterosaurs to a new method of locomotion. The earliest known pterosaurs took flight and subsequently appear to have become capable and efficient flyers. However, it seems clear that transitioning between forms of locomotion2,3—from terrestrial to volant—challenged early pterosaurs by imposing a high energetic burden, thus requiring flight to provide some offsetting fitness benefits. Using phylogenetic statistical methods and biophysical models combined with information from the fossil record, we detect an evolutionary signal of natural selection that acted to increase flight efficiency over millions of years. Our results show that there was still considerable room for improvement in terms of efficiency after the appearance of flight. However, in the Azhdarchoidea4, a clade that exhibits gigantism, we test the hypothesis that there was a decreased reliance on flight5–7 and find evidence for reduced selection on flight efficiency in this clade. Our approach offers a blueprint to objectively study functional and energetic changes through geological time at a more nuanced level than has previously been possible.