Uit New Mexico werden in 1916 voor het eerst door Charles Whitney Gilmore ankylosaurische fossielen gemeld, waaronder een rechteropperarmbeen. Deze en opvolgende vondsten werden tot het midden van de jaren negentig meestal toegewezen aan Euoplocephalus tutus, net als bijna al het Noord-Amerikaanse ankylosauride materiaal uit het Campanien.
In augustus 1995 groef paleontoloogRobert Michael Sullivan bij de Willow Wash nabij Farmington in San Juan County skeletten van Parasaurolophus op. Enkele honderden meters ten westen van deze groeve vond hij bij toeval de verweerde schedel van een ankylosauriër uit de bodem steken. Omdat hij zijn handen vol had aan de andere opgraving, en de vondst van slechte kwaliteit was, liet hij die voorlopig in de grond zitten maar in 1996 keerde Sullivan terug en stelde de schedel veilig met behulp van Kesler Randall, de preparateur van het San Diego Natural History Museum. De schedel was de eerste van een ankylosauriër die in het zuidwesten van de Verenigde Staten van Amerika was gevonden. Na preparering van het fossiel kwam hij tot de conclusie dat het duidelijk niet om Euoplocephalus ging.
In 1999 benoemde en beschreef Sullivan de typesoortNodocephalosaurus kirtlandensis. De geslachtsnaam is afgeleid van het Latijnsenodus, "knobbel", en het Oudgriekse κεφαλή, kephalè, "hoofd", en is een verwijzing naar het knobbelige huidpantser op de kop. De soortaanduiding verwijst naar de herkomst uit de Kirtlandformatie.
Het holotype, SMP VP-900, is opgraven in een laag moddergesteente van de De-na-zin-afzetting van de Kirtlandformatie die dateert uit het late Campanien, ongeveer drieënzeventig miljoen jaar oud. Het bestaat uit een schedel zonder onderkaken. Door de verwering is niet heel veel detail zichtbaar. Het fossiel maakt deel uit van het State Museum of Pennsylvania. Sullivan wees in eerste instantie geen andere fossielen aan de soort toe, omdat een verband gezien het gebrek aan overlappend materiaal niet bewezen kon worden. Later waren hij en andere onderzoekers echter niet zo voorzichtig. Toegewezen werden uiteindelijk: NMMNH P-27404: een schub van een halsborg; NMMNH P-27405: osteodermen; SMP VP-1149: een staartwervel; SMP VP-1743: een eerste staartwervel; SMP VP-1646: een staartknots; SMP VP-1870: een linkerstekel van een halsborg; SMP VP-2074: pantserplaten en stukken staartknots; SMP VP-1957: twee osteodermen van de schedel; en SMP VP-1632: stukken staartknots. Behalve SMP VP-1957 waren al deze toewijzingen puur gebaseerd op de herkomst. In 2014 werd echter uit dezelfde lagen de verwant Ziapelta benoemd; de andere vondsten kunnen dus ook daaraan toebehoren.
Beschrijving
Het holotype van Nodocephalosaurus is een middelgrote ankylosauride. In 2010 schatte Gregory S. Paul de lichaamslengte op vierenhalve meter, het gewicht op anderhalve ton.
Volgens Sullivan onderscheidt Nodocephalosaurus zich door een richelvormige osteoderm achter de zone van het bovenkaaksbeen en traanbeen en verder door een grote, naar voren en beneden uitstekende, osteoderm op het quadratojugale, op de onderkant van de achterste schedel. Daarnaast bevinden zich gezwollen of bultvormige veelhoekige osteodermen op de snuit, geordend in een symmetrisch patroon aan weerszijden van de middenlijn. In 2014 werd Ziapelta beschreven; deze vorm heeft vrij platte osteodermen. Beide soorten hebben grote naar bezijden en achteren uitstekende "hoorns" op de hoeken van het achterhoofd gemeen, op de squamosa. Bij Nodocephalosaurus heeft de hoorn een plat bovenvlak die via een ribbe overgaat in het zijvlak. Bij Ziapelta bevindt zich een scherpe richel op het bovenvlak. Een andere verschil is dat bij Nodocephalosaurus de snuit korter is en naar voren sterk vernauwt.
De schedel heeft een lengte van ongeveer vijfenveertig centimeter. Sommige osteodermen hebben een piramidevormige welving. Naast de neusholte, en ermee verbonden, bevindt zich een holte in het bovenkaaksbeen.
Fylogenie
Sullivan plaatste Nodocephalosaurus in de Ankylosauridae. Volgens hem waren ze nauwer verwant aan de Aziatische Saichania chulsanensis en Tarchia gigantea dan aan bekende Amerikaanse vormen. Volgens sommige analyses is Nodocephalosaurus een lid van de Ankylosaurinae.
Het onderstaande kladogram geeft een mogelijke positie van Nodocephalosaurus in de evolutionaire stamboom van de Ankylosauridae.
R.M. Sullivan, 1999, "Nodocephalosaurus kirtlandensis, gen. et sp. nov., a new ankylosaurid dinosaur (Ornithischia: Ankylosauria) from the Upper Cretaceous Kirtland Formation (Upper Campanian) San Juan Basin, New Mexico", Journal of Vertebrate Paleontology19(1): 126-139
Robert M. Sullivan and Denver W. Fowler, 2006, "New specimens of the rare ankylosaurid dinosaur Nodocephalosaurus kirtlandensis (Ornithischia: Ankylosauridae) from the Upper Cretaceous Kirtland Formation (De-na- zin Member), San Juan Basin, New Mexico", In: Lucas, S. G. and Sullivan, R.M., (eds.), Late Cretaceous vertebrates from the Western Interior. New Mexico Museum of Natural History and Science Bulletin 35 p. 259-261