The specific localities in which they were discovered, represent the Middle Member of the Tlayúa Formation,[1] a Lagerstätte rich in vertebrate fossils.

The generic name comes from the Nahuatl words huehuetl ("the ancient") and cuetzpalli ("lizard"), while the specific name refers to the La Mixteca region.

Describing Huehuecuetzpalli in 1998, Reynoso ran a phylogenetic analysis, wherein the most parsimonious tree recovered it as the outgroup of crown-group squamates.

This conclusion was supported by the facts that its premaxillae were still divided, that its vertebrae were still amphicoelous (concave on both ends), similar to those of certain geckos, and that it retained a second distal tarsal, among other characters suggestive of a fairly basal position.

[1] The tree recovered by Reynoso is below:Huehuecuetzpalli Agamidae Chamaeleontidae Iguanidae Cordylidae Scincidae Gymnophthalmidae Teiidae Lacertidae Xantusiidae Amphisbaenia Dibamidae Gekkonidae Pygopodidae Serpentes Anguidae Xenosauridae Helodermatidae Lanthanotus Varanus A fairly basal position has been supported by subsequent papers.

However, the ziphodont (laterally compressed and serrated) teeth of varanids are absent: those of Huehuecuetzpalli were instead peg-like, suggesting that it may instead have fed on smaller prey, such as insects.