We describe a Paleocene-Eocene pelomedusoid turtle from tropical South America in a new fossiliferous locality, from Los Cuervos Formation, at the Calenturitas Coal Mine, Colombia. Although no further systematic precision beyond Pelomedusoides incertae sedis can be supported, the presence of an ischial scar positioned far anteriorly to the anal notch, and a strongly decorated ventral surface of the plastron, indicate that this specimen is potentially related to the bothremydid clade formed by Puentemys-Foxemys. We also demonstrate the potential organic preservation of osteocytes and blood vessels for this specimen, indicating that preservation of soft tissue such as vessels and bone cells in the fossil record is independent of bone type, fossil site, or locality; occurring in different lineages of vertebrates; and that it is even possible to occur in tropical depositional environments during a period of maximum global warming such as the Paleocene-Eocene.