The genus and type species was based upon ribs, vertebrae, a fore-paddle and fragments of the pectoral girdle discovered in Wyoming, USA in 1895. The species named as Megalneusaurus rex (meaning "great swimming lizard King") in 1898. However some of this material has since been lost, although new material has been discovered from the same site. Based upon the bones very large size, it appears to have grown to a size comparable to Liopleurodon.
Material from southern Alaska have been referred to Megalneusaurus, although this material is from an individual of much smaller size.