Patagosuchus is known solely from its holotype, MANE-PV 1, which consists of some associated bones belonging to a single individual. The remains include a fragmentary left dentary and splenial, the right maxilla and right jugal bone, a back vertebra, a back osteoderm and the right humerus. MANE-PV 1 was discovered at the Baal Quarry, in the Loma de La Lata area, near the northern coast of Lago Los Barreales, 12 km south of Añelo City, southeastern Neuquén Province of Patagonia. It was collected from the Portezuelo Formation which is the older of the two formations in the Río Neuquén Subgroup, of the Neuquén Group, dating to the late Turonian to early Coniacian of the early Late Cretaceous. Patagosuchus is the second peirosaurid described from this formation, along with Lomasuchus palpebrosus. Patagosuchus represents the third peirosaurid named from the Neuquén Group, with Gasparinisuchus peirosauroides known from the younger Santonian to early Campanian Bajo de la Carpa and Anacleto Formations,^[1] and the more recently named Bayomesasuchus hernandezi from the underlying late Cenomanian to early Turonian Cerro Lisandro Formation representing the fourth.^[2] These represent the five known Patagonian peirosaurids, together with Barcinosuchus gradilis from the Aptian to Albian Cerro Barcino Formation of Chubut Group.^[1]

Patagosuchus was first described and named by Gabrel Lio, Federico L. Agnolína, Rubén Juarez Valieri, Leonardo Filippi and Diego Rosales in 2015 and the type species is Patagosuchus anielensis. The generic name refers to Patagonia, and suchus, Latinized from the Greek souchos, an Egyptian crocodile god. The specific name refers to the city of Añelo, near which the holotype was discovered and collected.