This paper presents a new titanosaur sauropod, collected from levels of reddish clays assigned to the Plottier Formation (Coniacian-Santonian). The holotype of Petrobrasaurus puestohernandezi gen. et. sp. nov. is a disarticulated specimen, from which teeth, cervical, dorsal and caudal vertebrae, sternal plates, metacarpals, femora, tibia, a fragment of ilium, pubis, haemal arches, and cervical and dorsal ribs have been preserved. This period is of particular interest because it saw the definitive isolation of the vertebrate faunas of Patagonia, with the separation of South America from the rest of Gondwana, a process that had begun during the Early Cretaceous. Although some of the characters observed in Petrobrasaurus gen. nov. suggest a relationship with the South American clade Lognkosauria, this new sauropod is regarded as Titanosauria incertae sedis until a more profound analysis of the Titanosauria that in which it is included is undertaken.