A new Late Cretaceous turtle, Angolachelys mbaxi gen. et sp. nov., from the Turonian (90 Mya) of Angola, represents the oldest eucryptodire from Africa. Phylogenetic analysis recovers Angolachelys mbaxi as the sister taxon of Sandownia harrisi from the Aptian of Isle of Wight, England. An unnamed turtle from the Albian Glen Rose Formation of Texas (USA) and the Kimmeridgian turtle Solnhofia parsonsi (Germany), are successively more distant sister taxa. Bootstrap analysis suggests those four taxa together form a previously unrecognized monophyletic clade of marine turtles, herein named Angolachelonia clade nov., supported by the following synapomorphies: mandibular articulation of quadrate aligned with or posterior to the occiput, and basisphenoid not visible or visibility greatly reduced in ventral view. Basal eucryptodires and angolachelonians originated in the northern hemisphere, thus Angolachelys represents one of the first marine amniote lineages to have invaded the South Atlantic after separation of Africa and South America.