We report a new pleurodiran turtle from the Barremian Morro do Chaves Formation, Sergipe-Alagoas Basin, Brazil. We tested the phylogenetic position of Atolchelys lepida gen. et sp. nov. by including it in a comprehensive cladistic analysis of pleurodires. The new species is a basal member of Bothremydidae and simultaneously the oldest unambiguous crown Pleurodira. The biogeographic and chronostratigraphic significance of the finding has implications for the calibration of molecular clocks studies by pushing back the minimum age of crown Pleurodira by more than 12 Ma (ca 125 Ma). The reanalysis of Pelomedusoides relationships provides evidence that the early evolution and relationships among the main lineages of side-necked turtles can be explained, at least partially, by a sequence of vicariance events.