It is known from a well-preserved skull that was collected by an American Museum of Natural History expedition to Mongolia in 1923 and cataloged as AMNH FR 21444.

After its initial cataloging, the specimen was not mentioned again in the scientific literature until 2004, when it was recognized as belonging to a potential early relative of modern groups of squamates such as gekkotans, amphisbaenians, dibamids, and snakes.

AMNH FR 21444 was more fully described in a 2006 study that used high-resolution computed tomography to examine the skull and its braincase,[1] and was described as a new genus and species, Norellius nyctisaurops, in 2015.

The 2006 study incorporated the specimen into a phylogenetic analysis and found it to be a basal member of an evolutionary grouping called Gekkonomorpha, a stem-based taxon that includes living geckos and legless lizards (pygopodids) and all taxa more closely related to them than to any other living lizard.

Norellius lies outside the node-based taxon Gekkota, a more strictly-defined subgroup of Gekkonomorpha that includes geckos, pygopodids, and all descendants of their most recent common ancestor.