A new stem cheloniid turtle, Cabindachelys landanensis, gen. et sp. nov., is represented by a nearly complete skull and partial hyoid collected in lower Paleocene shallow marine deposits, equivalent to the offshore Landana Formation, near the town of Landana in Cabinda, Angola. A partial chelonioid carapace previously reported from this locality is referred here to C. landanensis. Cabindachelys landanensis possesses clear synapomorphies of Pan-Cheloniidae, including a rod-like rostrum basisphenoidale, V-shaped basisphenoid crest, and secondary palate, but differs from most other pan-cheloniids in that the foramen palatinum posterius is present. Phylogenetic analysis suggests that C. landanensis forms a weakly-supported clade with Erquelinnesia gosseleti, Euclastes acutirostris, Euclastes wielandi, and Terlinguachelys fischbecki, although a close relationship between the protostegid T. fischbecki and these durophagous pan-cheloniids is unlikely. The Paleocene–Eocene strata near Landana have produced a number of turtle fossils, including the holotype specimen of the pleurodire Taphrosphys congolensis. A turtle humerus collected approximately 1 meter above the holotype skull of C. landanensis differs from humeri of chelonioids and Taphrosphys, indicating that a third turtle taxon is present at Landana. Cheloniid fossil material is rare in the Landana assemblage, in comparison with the abundant remains of Taphrosphys congolensis found throughout the stratigraphic section. This disparity implies that C. landanensis preferred open marine habitats, whereas Taphrosphys congolensis spent more time in nearshore environments. The appearance of new durophagous species such as C. landanensis in the early Paleocene reflects the rapid radiation of pan-chelonioids as they diversified into open niches following the K–Pg extinction.