On trouve les ancêtres des vertébrés terrestres dans un autre groupe de poissons osseux appelés les Choanichthyes ou Sarcopterygii. Les poissons choanates sont caractérisés par des narines internes, des nageoires charnues appelées nageoires lobées, et des écailles cosmoïdes. Les poissons choanates apparurent à la fin du Silurien ou au début du Dévonien, il y a plus de 390 millions d'années, et dérivent probablement des acanthodiens. Les poissons choanates incluent un groupe connu sous le nom de Crossopterygii, qui possède un représentant encore vivant, le cœlacanthe (genre Latimeria). Au cours du Dévonien, certains crossoptérygiens de l'ordre (ou sous-ordre) des Rhipidistia ont commencé à ramper hors de l'eau et devinrent les premiers tétrapodes.
L'histoire évolutive des vertébrés a commencé dans les mers du Cambrien, lorsque des créatures au corps mou, sans machoires et sans dents, se débattaient dans l'eau, en avalant des particules de nourriture microscopiques. Ce n'est qu'après que les os résistants ont été mis au point (initialement sous la forme d'une carapace écailleuse puis plus tard à l'intérieur du corps) que les formes fossiles purent être conservées dans les roches. Et ce n'est qu'à ce moment que les paléontologistes purent commencer à appréhender l'histoire avec une certaine assurance.
Les premières traces d'écailles osseuses ont été trouvées dans des roches datant de la fin du Cambrien, et les premières formes de poissons vertébrés reconnaissables ont été découvertes dans des roches en Australie datant du début de l'Ordovicien. Ainsi, le premier chapître de l'évolution des vertébrés a débuté avec le très ancien Arandaspis, un poisson d'environ 15 cm de long et dépourvu de machoires, sans dents et sans autre nageoire que la nageoire caudale. Il possédait cependant des branchies et une colonne dorsale formée de matériaux cartilagineux (la notochorde) qui lui servait d'épine dorsale.