300px|vignette|Squelette reconstitué d'un T. rex (KUVP 5033, surnommé « Bunker ») au dans le Colorado.
L’histoire des recherches sur Tylosaurus est particulièrement complexe en raison de son riche passé à la fois taxonomique et culturel. Les premiers signalements de fossiles attribués au genre remontent à 1869, lorsqu'Edward Drinker Cope décrit un spécimen partiel ayant été découvert au Kansas, aux États-Unis. Initialement nommé Macrosaurus proriger, l'espèce est par la suite transféré par Cope dans le genre Liodon. Au cours des années suivantes, ce dernier décrit deux autres espèces qu'il attribue également à ce genre. En 1872, Othniel Charles Marsh érige le genre Tylosaurus, dont le nom signifie littéralement « lézard bouton » en référence à la morphologie rostrale de l'animal, afin d'y inclure une espèce qu'il avait décrite antérieurement ainsi que deux des espèces décrites par Cope. Cette appellation commence à être utilisée dès l'année suivante par Joseph Leidy, bien que Cope, alors en rivalité avec Marsh, ne l'adopte pas. En 1894, John Campbell Merriam transfère définitivement chez Tylosaurus les espèces de Liodon décrites par Cope et Marsh. L'une d'elles est ensuite placée en synonymie avec l'espèce type T. proriger par Dale A. Russell en 1967.
En 1870, Cope décrit Tylosaurus comme un imposant reptile marin à l'allure comparable à celle d'un serpent de mer et dont la taille aurait égalé celle des plus grands cétacés, une interprétation reprise dans plusieurs œuvres de paléoart de l'époque. Dans une importante révision publiée en 1898, Samuel Wendell Williston présente une reconstitution squelettique bien plus précise de l'animal, toujours considérée comme globalement exacte selon les standards actuels. Du au , plusieurs espèces de mosasauridés aujourd'hui attribuées à Tylosaurus sont initialement décrites dans des genres distincts. L'un d'eux, Hainosaurus, est d'ailleurs considéré comme un synonyme plus récent de Tylosaurus depuis une étude publiée en 2016, bien que certains auteurs proposent de le maintenir comme un genre distinct et valide. Neuf espèces de Tylosaurus sont actuellement reconnues, à savoir T. proriger, T. nepaeolicus, T. bernardi, T. gaudryi, T. ivoensis, T. iembeensis, T. pembinensis, T. saskatchewanensis et T. rex. La validité de deux taxons supplémentaires demeure toutefois incertaine : T. kansasensis fait toujours l'objet d'un débat quant à sa possible synonymie avec T. nepaeolicus, tandis que T. borealis n'a pas encore fait l'objet d'une description formelle dans une publication scientifique.
Découverte initiales Possibles trouvailles antérieures Plusieurs fossiles provenant possiblement de Tylosaurus auraient été découverts bien avant que le genre ne soit formellement décrit et nommé dans la littérature scientifique, faisant potentiellement de ce dernier le premier mosasaure connu. La découverte de ses fossiles aurait influencé les récits folkloriques présents chez certains peuples amérindiens. La plus ancienne possible découverte le concernant aurait été faite par le peuple nord-amérindiens des Lenapes, bien avant l'arrivée des colons européens, soit aux alentours d'avant les années 1500. En effet, une ancienne légende rapporte que des chasseurs auraient découvert un fragment osseux appartenant à un monstre responsable de la mort de plusieurs personnes dans une région correspondant aux actuels Philadelphie, Pennsylvanie ou encore le New Jersey. Après avoir rapporté l'os dans leur village, ils auraient été encouragés par un sage local à rechercher d'autres restes de cette même créature. Selon ce dernier, le fait de fumer l'os avec du tabac procurerait divers bienfaits, tels qu'une bonne santé pour les enfants, une longue vie ou encore le succès à la chasse. Des fossiles de Tylosaurus ont effectivement été découverts dans la région d'où cette légende serait originaire. Toutefois, des restes de dinosaures et de crocodiliens datant du Crétacé y sont également connus, rendant ainsi l'identification du fossile à l'origine du récit incertaine.
À une époque plus récente, aux alentours des années 1600, les peuples Dakotas et Cheyennes évoquent un âge ancien durant lequel de gigantesques créatures aquatiques s'affrontaient continuellement avec des oiseaux-tonnerres. Selon ces récits, les monstres aquatiques auraient été pétrifiés par la foudre lancée par ces derniers, leurs restes pouvant dès lors être retrouvés dans le sol. Les récits fournis par les peuples Pawnees et Crows mentionnent également l'existence de créatures aquatiques similaires vivant dans les cours d'eau. Celles-ci sont décrites comme possédant une tête rappelant celle d'un crocodile, un corps serpentiforme et des membres prenant la forme de pattes voire de nageoires. Les Grandes Plaines, territoire occupé par les peuples à l'origine de ces récits, ont livré de nombreux fossiles de grands mosasaures tels que Tylosaurus ainsi que de ptérosaures comme Pteranodon, lesquels pourraient avoir inspiré ces légendes.
La première possible découverte enregistrée d'un mosasaure en Amérique du Nord est celle d'un squelette partiel décrit comme celui d'un « poisson » en 1804 par Meriwether Lewis et le Corps of Discovery de William Clark lors de leur expédition menée de 1804 à 1806 à travers l'ouest des États-Unis. Le squelette est découvert par le sergent américain sur des falaises de soufre noir près de l'île Cedar, le long de la rivière Missouri, et se composait de quelques dents et d'une colonne vertébrale désarticulée notée comme mesurant de longueur. Quatre membres de l'expédition ont enregistré la découverte dans leurs journaux, dont Clark et Gass.. Certaines parties du fossile ont été collectées et envoyées à Washington, où elles ont été perdues avant qu'une documentation appropriée puisse être établie. En 2003, le biologiste marin américain Richard Ellis émet l'hypothèse que les restes pourraient avoir appartenu à Mosasaurus missouriensis. Néanmoins, en 2007, le paléontologue concitoyen Robert W. Meredith et ses collègues suggèrent que les fossiles proviendraient d'un mosasaure de type tylosauriné en raison des mensurations citées par Clark et Gass et de la présence avérée de fossiles de Tylosaurus découverts ultérieurement dans le Missouri. Néanmoins, les auteurs mentionnent aussi la possibilité que les restes proviendraient d'un plésiosaure de type élasmosauridé, qui sont également connus dans cette rivière, bien que plus rares..
En 1858, le géologue américain Ebenezer Emmons décrit une dent unique de mosasaure comme représentant un nouveau genre et une nouvelle espèce, qu'il nomme Elliptonodon compressus.. En 1967, le paléontologue américain Halsey W. Miller examine le moulage du spécimen type, enregistré sous le numéro USNM 7444 au musée national d'histoire naturelle des États-Unis, et l'attribue provisoirement à Tylosaurus? sp., en se fondant sur les similitudes supposées entre cette dent et une dent antérieure d'une mâchoire de Tylosaurus conservée dans le même établissement sous le numéro USNM 3763.. La même année, le paléontologue canadien Dale A. Russell estime au contraire que le spécimen type ressemble davantage à une dent de Prognathodon. Il souligne toutefois que le fossile est trop fragmentaire et que sa provenance demeure incertaine, concluant qu’E. compressus doit être considéré comme un nomen dubium.
Premières découvertes formelles et dénomination vignette|gauche|redresse=1.3|Le spécimen holotype de T. proriger (MCZ VPRA 4374), tel qu'illustré par Cope en 1870.
Tylosaurus est le troisième genre de mosasaures décrit en Amérique du Nord après Clidastes et Platecarpus, ainsi que le premier identifié au Kansas. Les débuts de son histoire taxonomique sont marqués par les complications liées à la célèbre rivalité opposant les paléontologues américains Edward Drinker Cope et Othniel Charles Marsh durant la guerre des os. Le spécimen holotype se compose d'un crâne partiel d'environ de long associé à treize vertèbres. L'histoire de sa découverte demeure en partie incertaine en raison de témoignages contradictoires et de données divergentes concernant la localité type. Ses premières mentions contemporaines remontent à la fin de l'année 1868 dans deux journaux régionaux du Kansas, où la découverte est attribuée au collecteur de fossiles américain William E. Webb, alors premier propriétaire connu du spécimen... La quasi-totalité des sources s'accordent néanmoins à considérer que celui-ci provient très probablement de la , une unité stratigraphique de la formation de Niobrara. Les archives du spécimen indiquent qu'il aurait été découvert près de , à l'ouest du comté de Gove. Néanmoins, en 1875, Cope précise toutefois que les fossiles auraient en réalité été découverts par le colonel de l'armée américaine John Butler Conyngham et un certain M. Minor, à proximité de la gare de , le long de la ligne ferroviaire du Kansas Pacific, dans l'ouest de l'État.. C'est cette dernière localisation qui est retenue comme la plus probable, bien que des futures études s'avèrent nécessaires pour le confirmer. Ce n'est qu'après cette découverte que le spécimen est obtenu en 1868 par Webb, vraisemblablement par l'intermédiaire de Conyngham, bien que les circonstances exactes de ce transfert demeurent incertaines.
En août de la même année, le naturaliste suisse Louis Agassiz et d'autres personnalité importantes traversent la ville de Monument. C'est probablement à cette occasion qu'Agassiz rencontre Webb, et peut-être également Conyngham, obtenant par la suite le spécimen, qu'il dépose au Musée de Zoologie comparée d'Harvard sous le numéro d'inventaire MCZ VPRA 4374, où il est toujours conservé. Le reçu attestant le versement de 500 $ de l'époque par Agassiz à Webb, daté du , est également conservé avec ce spécimen. Celui-ci comprend en outre la sixième dent du maxillaire droit, incorrectement cataloguée sous le numéro MCZ 1596, alors que le véritable numéro d'inventaire figure sur les autres éléments fossiles. Lors de la réunion de l'Académie des sciences naturelles de Philadelphie du , le paléontologue américain Joseph Leidy présente des photographies du spécimen que Webb lui a adressées, l'identifiant provisoirement comme appartenant au genre Mosasaurus.. C'est durant cette même réunion que Cope remarque très probablement ces memes photographies., empruntant ensuite le spécimen concernée à Agassiz et en présentant une première description lors d'une autre réunion de l'institution en juin de l'année suivante. La première publication de Cope concernant ce spécimen est très brève, le nommant Macrosaurus proriger, Macrosaurus étant alors un genre européen déjà existant de mosasaure.. L'épithète spécifique proriger, signifiant « portant de proue », fait référence au rostre allongé du spécimen rappelant une proue de navire, et dérive du latin « proue » et du suffixe « porter ».. En 1870, Cope publie une description plus détaillée du spécimen MCZ 4374. Sans fournir d'explication, il transfère alors l'espèce dans un autre genre européen, Liodon, et considère M. proriger comme un synonyme.. Dans ses descriptions de 1870 et 1875, Cope mentionne et illustre plusieurs vertèbres supplémentaires qu'il attribue au spécimen type. Toutefois, ces éléments n'étant pas associés au spécimen tel qu'il est actuellement conservé, il demeure impossible de déterminer s'ils ont été perdus ou s'ils n'ont, en réalité, jamais fait partie de l'holotype.