A new species of limestone cave-adapted gecko of the Cyrtodactylus pulchellus complex, C. hidupselamanya sp. nov., is described from an isolated karst formation at Felda Chiku 7, Kelantan, Peninsular Malaysia. This formation is scheduled to be completely quarried for its mineral content. From what we know about the life history of C. hidupselamanya sp. nov., this will result in its extinction. A new limestone forest-adapted species, C. lenggongensis sp. nov., from the Lenggong Valley, Perak was previously considered to be conspecific with C. bintangrendah but a re-evaluation of morphological, color pattern, molecular, and habitat preference indicates that it too is a unique lineage worthy of specific recognition. Fortunately C. lenggongensis sp. nov. is not facing extinction because its habitat is protected by the UNESCO Archaeological Heritage of the Lenggong Valley due to the archaeological significance of that region. Both new species can be distinguished from all other species of Cyrtodactylus based on molecular evidence from the mitochondrial gene ND2 and its flanking tRNAs as well as having unique combinations of morphological and color pattern characteristics. Using a time-calibrated BEAST analysis we inferred that the evolution of a limestone habitat preference and its apparently attendant morphological and color pattern adaptations evolved independently at least four times in the C. pulchellus complex between 26.1 and 0.78 mya.