The two living groups of flying vertebrates, birds and bats, both have constricted genome sizes compared with their close relatives. But nothing is known about the genomic characteristics of pterosaurs, which took to the air over 70 Myr before birds and were the first group of vertebrates to evolve powered flight. Here, we estimate genome size for four species of pterosaurs and seven species of basal archosauromorphs using a Bayesian comparative approach. Our results suggest that small genomes commonly associated with flight in bats and birds also evolved in pterosaurs, and that the rate of genome-size evolution is proportional to genome size within amniotes, with the fastest rates occurring in lineages with the largest genomes. We examine the role that drift may have played in the evolution of genome size within tetrapods by testing for correlated evolution between genome size and body size, but find no support for this hypothesis. By contrast, we find evidence suggesting that a combination of adaptation and phylogenetic inertia best explains the correlated evolution of flight and genome-size contraction. These results suggest that small genome/cell size evolved prior to or concurrently with flight in pterosaurs. We predict that, similar to the pattern seen in theropod dinosaurs, genome-size contraction preceded flight in pterosaurs and bats.