Mesoclemmys is the most diverse extant genus of South American pleurodires or side-necked turtles, with at least 10 species inhabiting fluvial to littoral environments. Despite this high extant diversity and extensive geographic distribution, the evolutionary history and fossil record of this genus are completely unknown. Here, we describe the first fossil record of this genus, which supports a previous molecular-based hypothesis that indicates a minimum split time of 13.5 Ma between this and other genera of South American chelids. Mesoclemmys vanegasorum, sp. nov., is represented by a nearly complete shell (carapace and plastron) and some postcranial bones found in the middle Miocene (13.6 ± 0.2 Ma), La Victoria Formation, Tatacoa Desert, Colombia, increasing the turtle paleodiversity of La Venta Fauna. It differs from all extant species of Mesoclemmys by vertebral scute 1 reaching the sutural boundary between peripherals 1 and 2; shorter cervical and marginal scutes 1 to 3; pleurals 1 very advanced over the peripherals; pygal bone with a posteromedial shallow notch; vertebral 5 covering half of the pygal bone; small extragulars reaching only half of the epiplastra length; and a fine microvermiculation of the shell. Our phylogenetic results show a close relationship between M. vanegasorum, sp. nov., and the extant M. hogei. The overall morphology and size of Mesoclemmys genus have remained relatively constant for at least the last 13.6 million years. However, its geographic distribution has decreased drastically in northwestern South America, being restricted today to the lower region of the Magdalena River Basin.