We report a new chelonioid turtle on the basis of a nearly complete skull collected in lower Paleocene, shallow marine deposits, equivalent to the offshore Landana Formation, near the town of Landana in Cabinda Province, Angola. Chelonioid material previously reported from this locality is likely referable to this new taxon. The well-preserved skull is missing the left quadrate, squamosal, and prootic, both opisthotics, and the mandible. The skull possesses a rod-like basisphenoid rostrum, which is a synapomorphy of Chelonioidea, but it differs from other chelonioid skulls in that the contact between the parietal and squamosal is absent, and the posterior palatine foramen is present. Phylogenetic analysis recovers the new taxon as a basal chelonioid. The Paleocene– Eocene strata near Landana have produced a wealth of turtle fossils, including the holotype of the pleurodire Taphrosphys congolensis. A turtle humerus collected from the Landana locality differs morphologically from the humeri of chelonioids and Taphrosphys, indicating the presence of a third taxon. Chelonioid fossil material in the Landana assemblage is rare compared to the abundant fragmentary remains of Taphrosphys that are found throughout the stratigraphic section. This disparity in abundance suggests the new chelonioid taxon preferred open marine habitats, whereas Taphrosphys frequented nearshore environments.