Herein, we describe Alatochelon myrteum gen. et sp. nov., a large tortoise from the post‐Messinian (lower Pliocene) of the area of Puerto de la Cadena (Region of Murcia), Spain. The new taxon cannot be attributed to Titanochelon, which represented the only lineage of large tortoises previously recognized in the Neogene record of Europe. Alatochelon myrteum shows African affinities, especially with the extant African spurred tortoise Centrochelys sulcata. Although close phylogenetic relationships have previously been recognized among some tortoises of both continents, the dispersal of this lineage had always been proposed as having occurred in only one direction: from Europe to Africa. The dispersal of the lineage including the new Spanish form and Centrochelys sulcata from Africa to Europe is proposed here. This proposal is compatible with those previously recognized for some lineages of mammals also found in Puerto de la Cadena, identified as African lineages that probably reached Europe during the Messinian Salinity Crisis event. An African origin is also proposed for the lineage of Titanochelon. Therefore, the two lineages of large derived testudinids (i.e. Geochelona) recognized in the European record experienced diachronic dispersal events from Africa to Europe: that to which Alatochelon belongs probably during the Messinian and the other much earlier, at the beginning of the Miocene or before.