Leaf-tailed geckos are a distinctive group of carphodactyline geckos of rainforests and rocky habitats of eastern Australia. Three genera are recognized: Phyllurus (9 species), Saltuarius (6 species) and Orraya (1 species). Leaf-tailed geckos have been the subject of much survey and taxonomic work because they are large, impressive geckos and generally have highly localized distributions. The six species comprising Saltuarius are distributed in rock outcrops and rainforests along the ranges from northern New South Wales to the Wet Tropics region of north-east Queensland. Here we report the discovery of a new Saltuarius species at Cape Melville, a rainforest outlier on Cape York Peninsula in north-east Queensland. The new species is assigned to Saltuarius based on morphological and genetic data. Saltuarius eximius sp. nov. is highly distinct from all congeners in many aspects of morphology. It has a very long slender form, with relatively longer limbs, longer body, narrower body and narrower neck than all congeners. It also has a highly distinct head that is relatively smaller than that of all other Saltuarius, with very large eyes that are grey rather than patterned. The tail is large but with a relatively short attenuated tip. Saltuarius eximius sp. nov. appears to be highly localized to upland rainforest associated with boulder habitat in the Cape Melville Range. The unusual elongate form and large eyes of S. eximius sp. nov. likely reflect adaptation to deep boulder habitat. Two other new vertebrate species (a skink and a frog) were discovered in the rainforest and boulder-fields of Cape Melville during recent surveys, bringing the number of vertebrates known to be endemic to the Cape Melville Range to six (three frogs, two skinks and one gecko).