The region of Borneo is very interesting in its diversity of gekkonid lizards of the genus Cyrtodactylus. Until now, it is known to harbor 14 described species. Herein, we described a new member of this genus from the adjacent island of Maratua. Cyrtodactylus tehetehe sp. nov. is named after the specialty of the traditional cuisine of the Derawan Islands (sticky rice with coconut milk and a little salt wrapped in sea urchin skin, Echinoidea spp.). The new species forms a tight phylogenetic clade with Philippine taxa allied to C. annulatus and is sister to the Palawan species C. tautbatorum, a biogeographic surprise, given that C. jambangan and C. annulatus occur closer geographically, in the Sulu Archipelago. The new species can be distinguished from all other congeners by a combination of characters including maximum SVL, number of supralabials, infralabials, longitudinal dorsal tubercle rows, paravertebral tubercles, ventral scale rows, subdigital lamellae on fourth toe, by having tubercles on ventrolateral body folds, a single precloacal pore and enlarged precloacal scales, lacking tubercles on upper arm, enlarged femoral scales and respective pores, precloacal depression, and transversely enlarged median subcaudals.