BackgroundBothremydidae is a clade of extinct pleurodiran turtles known from the Cretaceous to Paleogene of Africa, Europe, India, Madagascar, and North and South America. The group is most diverse during the Late Cretaceous to Paleogene of Africa. Little is known, however, about the early evolution of the group.MethodsWe here figure and describe a fossil turtle from early Late Cretaceous deposits exposed at MacFarlane Mine in Cedar Canyon, southwestern Utah, USA. The sediments associated with the new turtle are utilized to infer its stratigraphic provenience and the depositional settings in which it was deposited. The fossil is compared to previously described fossil pleurodires, integrated into a modified phylogenetic analysis of pelomedusoid turtles, and the biogeography of bothremydid turtles is reassessed. In light of the novel phylogenetic hypotheses, six previously established taxon names are converted to phylogenetically defined clade names to aid communication.ResultsThe new fossil turtle can be inferred with confidence to have originated from a brackish water facies within the late Cenomanian Culver Coal Zone of the Naturita Formation. The fossil can be distinguished from all other previously described pleurodires and is therefore designated as a new taxon,Paiutemys tibertgen. et. sp. nov. Phylogenetic analysis places the new taxon as sister to the EuropeanPolysternon provinciale,Foxemys trabantiandFoxemys mechinorumat the base of Bothremydinae. Biogeographic analysis suggests that bothremydids originated as continental turtles in Gondwana, but that bothremydines adapted to near-shore marine conditions and therefore should be seen as having a circum-Atlantic distribution.