We describe a new species of the genus Cyrtodactylus based on six adult specimens from Lac Dao forests, Phu Yen Province, southern Vietnam. Cyrtodactylus tayhoaensis sp. nov. is distinguished from the remaining Indochinese bent-toed geckos by a combination of the following characters: medium size (SVL up to 94.2 mm); nasal scales 5-6; internasal single or double; ciliaria 29-34; dorsal tubercles in 20-22 irregular transverse rows; ventral scale in 37-41 longitudinal rows at midbody; ventrolateral folds present without interspersed tubercles; precloacal pores absent in females, precloacal pores 4 or 5 in males; 10 or 11 enlarged femoral scales on each thigh; femoral pores 3-7 in males, absent in females; postcloacal tubercles 3 or 4; lamellae under toe IV 22-24; dorsal pattern consisting of unclear transverse bands formed by irregularly shaped dark-brown blotches, a discontinuous neckband with V-shape or triangle shape in the middle, dorsal head surface with dark-brown blotches; subcaudal scales transversely enlarged. In the phylogenetic analyses, the new species is recovered as a sister taxon to C. kingsadai with approximately 4% genetic divergence between the two species based on a fragment of the COI gene. This is the second species of Cyrtodactylus known from Phu Yen Province located in southern Vietnam.