Two new alcyonacean-associated species, Hamodactylus paraqabai sp. nov. from Papua New Guinea and the Great Barrier Reef and H. pseudaqabai sp. nov. from Indonesia and Malaysia, are described and illustrated. To evaluate the status of the new species and their relationship within the genus Hamodactylus Holthuis, 1952, we combined morphology and phylogenetic analyses based on the cytochrome c oxidase subunit I (COI) mitochondrial gene. Both new species are closely related, with their mutual genetic divergence reaching 3-4%. They are further most related to Hamodactylus aqabai Bruce & Svoboda, 1983, originally described from the Red Sea. Both new species are distinguished from all other congeners by the presence of multiple teeth distally on the cutting edges of the fingers of the first pereiopods, and, in the case of H. paraqabai sp. nov., by a full reduction of the fixed finger on the second pereiopod chela. In H. pseudaqabai sp. nov. the finger is greatly reduced to a small but distinct stub, and the telson bears only a single pair of dorsal spines, as in H. aqabai. A key for the identification of all six currently known species is proposed.