Los fósiles de la parte anterior de un hocico de plesiosaurio fueron descubiertos en 2000 en la propiedad de Jorge Muñoz, en Loma La Cabrera, cerca de Villa de Leyva en Boyacá, Colombia, en terrenos de origen marino que datan de la época del Barremiense del Cretácico. Muñoz reportó el hallazgo a las autoridades locales, que a su vez dieron aviso al personal del Museo Geológico José Royo y Gómez del Servicio Geológico Colombiano en Bogotá. La excavación del esqueleto casi completo se produjo entre 2004 a 2005, con colaboración de la Fundación Colombiana de Geobiología, siendo luego trasladados los restos a Bogotá, asignándosele el número de catálogo VL17052004-1, para su preparación y estudio. Los restos fueron hallados articulados en su mayor parte en el Segmento C del miembro Arcillolitas Abigarradas de la Formación Paja, en una arcillolita caolínitica que corresponde a un ambiente marino intermareal, junto a varios ejemplares de amonites o impresiones de estos en la matriz rocosa, incluyendo uno dentro del cráneo. Estos amonites incluyen a las especies Gerhardtia galeatoides, G. provincialis y al género Heinzia, propios del Barremiense. El paleontólogo alemán Oliver Hampe realizó una descripción inicial del espécimen en 2005, clasificándolo como Brachauchenius sp., es decir, como una especie indeterminada de ese género, antes solo registrado en el Cretácico Superior de Estados Unidos, y constituiría la primera reaparición de pliosaurios no romaleosáuridos después de un hiato entre el Berriasiense y el Hauteriviense.[2] En 2016 María Páramo, Marcela Gómez-Pérez, Leslie Noé y Fernando Etayo realizaron una descripción más completa y designaron a VL17052004-1 como holotipo de un nuevo género y especie, Stenorhynchosaurus munozi. El nombre del género deriva de las palabras griegas stenos, "estrecho"; rhyncho, "hocico" y saurus, "lagarto", mientras que el nombre de la especie, munozi es en reconocimiento de Jorge Muñoz por descubrir y reportar el fósil.[1]