Molecular and morphological analyses indicate that a new upland species of the Cyrtodactylus sworderi complex, C. tebuensis sp. nov. from Gunung Tebu, Terengganu, Malaysia is most closely related to C. sworderi and together they form the sister lineage to C. quadrivirgatus. Cyrtodactylus tebuensis sp. nov. is differentiated from all other species of Sundaland Cyrtodactylus on the basis of having the unique combination of large, conical, keeled body tubercles; tubercles present on top of head, occiput, nape, and limbs, and extending posteriorly beyond base of tail; 43-51 ventral scales; no transversely enlarged, median subcaudal scales; proximal, subdigital lamellae transversely expanded; 17-21 subdigital lamellae on fourth toe; an abrupt transition between posterior and ventral femoral scales; enlarged femoral scales; no femoral or precloacal pores; no precloacal groove; body bearing four wide, bold, dark brown stripes (lateral stripe on each flank and a pair of paravertebral stripes); and a pairwise sequence divergence of 13.0% from its closest relative C. sworderi based on the mitochondrial gene ND2. Cyrtodactylus tebuensis sp. nov. is the first endemic upland species of gekkonid from northeastern Peninsular Malaysia and underscores the necessity for additional field work in all upland systems.