We describe Eremiascincus erebos sp. nov., a new species of banded, crepuscular and nocturnal skink from sandstone habitats of the southern Gulf of Carpentaria region in the Northern Territory, Australia. The species is known to inhabit scree and deep, cave-like crevices in gorges and rock towers. Morphology and genomic sequence data indicate E. erebos sp. nov. is most closely related to E. fasciolatus—with which it shares divided posterior supralabials, a character otherwise absent in Eremiascincus—but differs in having a larger ear opening, no ridges along the dorsal surfaces of the hindbody and tail, and a higher midbody scale row count. Although currently known from only two localities in the north-eastern Northern Territory, E. erebos sp. nov. is likely more widespread across the region south of the Gulf of Carpentaria.