It is known from a partial skeleton found at the Gadoufaoua locality in the western Ténéré Desert, in rocks of the Aptian–Albian-age Elrhaz Formation.

The holotype skeleton, MNN GAD1, includes a maxilla (main tooth-bearing bone of the upper jaw), vertebrae, ribs, and articulated pelvic girdle and sacrum, belonging to an adult about 6–7 m (19.7–23.0 ft).

[1] According to the describers, this specimen represents one of the earliest-known abelisaurids, and is notable for the heavily textured surface of the maxilla; the presence of pits and impressions of blood vessels indicates that there was a covering firmly attached to the face, perhaps of keratin.

This was based on several features, including a maxilla textured externally by impressed vascular grooves and a narrow antorbital fossa, that clearly place Kryptops palaios within Abelisauridae as its oldest-known member.

[1] Matthew Carrano et al. (2012), on the other hand, considered Kryptops palaios to be a chimera, and state that its postcranial remains (especially a pelvis and sacrum), found some 15 metres from the holotypic maxilla, actually belong to a carcharodontosaurid (possibly to Eocarcharia dinops).