Limestone and marl from Maria Farinha Formation (Paraíba Basin, NE Brazil) accumulated in a shallow continental shelf environment during the expansion of the Atlantic Ocean in early Paleocene (Danian). It contains a rich paleontological record, which comprises many marine invertebrates, several species of bony and cartilaginous fishes, a crocodyliform and turtle remains. Here, we describe a new genus and species of pleurodire turtle from Maria Farinha Formation, based on a nearly complete plastron, an incomplete left pelvic girdle, and four dermal plates of the carapace. We tested the phylogenetic position of Inaechelys pernambucensis gen. et sp. nov. by including it in a comprehensive cladistic analysis of pleurodires. The new species is included within Botrhemydidae, with affinities to Bothremydini, positioned as sister group of Rosasia soutoi. Inaechelys pernambucensis gen. et sp. nov. differs from R. soutoi for the almost straight anterior lobe cranial edge of its plastron, as well as for its pentagonal shaped entoplastron and its abdominal shield midline, which is considerably smaller than the respective femoral shield midline. Inaechelys pernambucensis is the first turtle species formally described from Brazilian Paleocene strata. Within Bothremydidae, it is also the first conclusively fully marine species described for this country. This new record contributes to the understanding of the ecology and paleobiogeographical distribution of Bothremydidae family.