Fossils from the front of a snout of a plesiosaur were discovered in 2000 on the property of Jorge Muñoz, in Loma La Cabrera, near Villa de Leyva in Boyacá, Colombia, on grounds of marine origin dating from the Late Barremian age of the Cretaceous. Muñoz reported the find to the local authorities, who in turn gave notice to staff of the Museo Geológico José Royo y Gómez administered by the Servicio Geológico Colombiano in Bogotá. Then was made the excavation of the nearly complete skeleton between 2004 and 2005, in collaboration with the Fundación Colombiana de Geobiología ("Colombian Geobiology Foundation"), and the remains being then transferred to Bogotá, assigning the catalog number VL17052004-1, for preparation and study.^[1]

The remains were found articulated mostly in the Segment C of the Arcillolitas Abigarradas Member of the Paja Formation, with kaolinitic argillite corresponding to an intertidal marine environment, with several specimens of ammonites or impressions of these in the rock matrix, including one inside the skull. These ammonites include the species Gerhardtia galeatoides, G. provincialis and the genus Heinzia, typical of the Barremian. German paleontologist Oliver Hampe made an initial description of the specimen in 2005, classifying it as Brachauchenius sp., i.e. as an indeterminate species of this genus, previously only recorded in Upper Cretaceous sediments of the United States, and it constitutes the first reappearance of non-rhomaleosaurid pliosaurs after a hiatus between the Berriasian and Hauterivian.^[3] In 2016, María Páramo, Marcela Gómez-Pérez, Fernando Etayo and Leslie Noé made a more complete description and they designated to VL17052004-1 as holotype of a new genus and species, Stenorhynchosaurus munozi.^[1]

The genus name is derived from the Greek words stenos, "narrow"; rhynchos, "snout" and sauros, "lizard", while the specific name munozi is in recognition of Jorge Muñoz by discover and report the fossil.^[1]