Extant sea turtles develop and lay pliable (flexible) eggs, however, it is unknown if they inherited this reproductive strategy from their closer fossil relatives or corresponds to an evolutionary novelty. Here we describe the first undisputable gravid marine fossil turtle ever found, from the early Cretaceous of Colombia, belonging to Desmatochelys padillai Cadena and Parham, which constitutes a representative of Protostegidae. Using thin sectioning of one the eggs, as well as scanning electron microscopy coupled with elemental characterization, cathodoluminescence, and computer tomography we established that Desmatochelys padillai produced rigid eggs similar to the ones found in some extant and fossil freshwater and terrestrial turtles, and that at least 48 spherical eggs are preserved inside this gravid turtle. We performed also a phylogenetic analysis of several turtle taxa, including some of the extant marine species, plus the information from the gravid specimen of Desmatochelys padillai, and we found more support to previous ideas that egg and eggshell characters lack of strong phylogenetic signal amongst turtle taxa. We suggest that the development of rigid eggs in the marine extinct turtle Desmatochelys padillai resulted as an adaptation for eggs-embryos requirements dictated by the physical attributes of the nesting site