Pan-trionychids (soft-shelled turtles) are known from the Neogene and Quaternary fossil record of Africa. They have so far been totally absent in Palaeogene localities of the continent although they are commonly found in Palaeogene localities across Europe, North America, and Australasia; as such, their absence from the Palaeogene of Africa has been envisaged to be genuine. Here, I describe a large costal from the Eocene of Mali, which documents for the first time the presence of pan-trionychid turtles in the Palaeogene of the then isolated Afro-Arabia. The affinities of the new Malian pan-trionychid with Neogene and Quaternary forms from Africa are discussed, as well as its biogeographic origins and potential dispersal scenarios from other landmasses to Afro-Arabia during the Palaeogene.