A new species of gecko of the genus Stenodactylus (Squamata: Gekkonidae) is described from the dune desert of Al Sharqiyah Sands in northeastern Oman. Stenodactylus sharqiyahensis sp. nov. is characterized morphologically by its small size, snout shape, webbing between fingers not very extended, relatively short limbs, and scalation. It is genetically distinct in the mitochondrial DNA and the nuclear MC1R gene from Stenodactylus arabicus to which it has previously been referred. The new species seems to have a restricted distribution confined to the Sharqiyah Sands, which remain isolated from other sand deserts in Arabia. In addition, the data presented herein confirm new locality records for Stenodactylus arabicus in the easternmost limit of its distribution range in western central Oman.