Study of new material collected in Oman by ultraviolet detection revealed three species of Vachoniolus, an unusual genus of psammophilous buthid scorpion distinguished by grossly swollen male pedipalp chelae. The presence of the type species, V. globimanus Levy, Amitai et Shulov, 1973, in Oman is confirmed, and two new species are described: V. batinahensis sp. nov. from the Al Batinah coastal plain north of the Al Hajar mountains, and V. gallagheri sp. nov. from desert alluvial fans south and west of the Al Hajar mountains. The number of Vachoniolus species is thereby raised to four, including V. iranus Navidpour et al., 2008, from northwestern Iran. Of these four, V. batinahensis appears the most plesiomorphic, with 7 external patellar trichobothria, femoral trichobothrium d5 either proximal or distal to e2, and complete retention of tibial spurs. It could be a relict descendent of an ancestral Vachoniolus population that evolved in the Tigris-Euphrates river drainage at a time when the Arabian Gulf was dry. A novel tarsal structure, the ‘spine comb’, is described in juvenile Vachoniolus, Apistobuthus and Odontobuthus. Possible mechanisms of sexual selection in the evolution of the enlarged male pedipalp chelae of Vachoniolus are discussed.