A major question in evolutionary biology is whether convergent phenotypes are driven by convergence at the level of the genome. We have approached this question by comparing genomes among palaeognathous birds, which include the volant tinamous of the New World and the flightless ratites (emu, ostrich, kiwi, etc), which are thought to have lost flight multiple times convergently. We produced 11 new high-quality palaeognath genomes, including a genome of an extinct moa from New Zealand, and aligned these to 32 additional genomes from birds and non-avian reptiles in an easily searchable genome browser. We called ~1.5 million conserved non-exonic elements (CNEEs) in these genomes, of which ~284,000 were greater than 50 bp, and, using a novel hierarchical Bayesian model, identified those undergoing relaxation or acceleration in individual ratite lineages or convergently in multiple ratite lineages. We also conducted extensive tests of adaptive evolution and pseudogenization across the palaeognath proteome to determine the potential contribution of coding regions to loss of flight. Whereas the evidence for pseudogenization in flightless birds is minimal and adaptive evolution among proteins modest (the transcription ZFHX4 and MGST2 show interesting ratite-specific signatures) we find that the ratites exhibit an unusually large number of accelerated CNEEs compared with other bird lineages, and that these CNEEs are often near genes with known roles in limb or skeletal development. ATAC-seq and enhancer screens reveal several CNEEs whose ability to drive gene expression in the avian forelimb has been lost in flightless birds. Overall our results suggest a strong role for non-coding regulatory evolution in the origin of flightlessness in palaeognathous birds.