Rich fossil evidence suggests that many traits and functions related to terrestrial evolution were present long before the ancestor of lobe- and ray-finned fishes. Here, we present genome sequences of the bichir, paddlefish, bowfin, and alligator gar, covering all major early divergent lineages of ray-finned fishes. Our analyses show that these species exhibit many mosaic genomic features of lobe- and ray-finned fishes. In particular, many regulatory elements for limb development are present in these fishes, supporting the hypothesis that the relevant ancestral regulation networks emerged before the origin of tetrapods. Transcriptome analyses confirm the homology between the lung and swim bladder and reveal the presence of functional lung-related genes in early ray-finned fishes. Furthermore, we functionally validate the essential role of a jawed vertebrate highly conserved element for cardiovascular development. Our results imply the ancestors of jawed vertebrates already had the potential gene networks for cardio-respiratory systems supporting air breathing. Comparative analyses of divergent lineages of ray-finned fishes reveal that that these species exhibit mosaic genomic features that have facilitated the adaptive evolution of phenotypes that contributed to the water-to-land transition.