A second species of the previously monotypic aphanodactylid crab genus Gustavus Ahyong & Ng, 2009 is described from the Red Sea coast of Saudi Arabia. The new species, Gustavus holthuisae sp. nov., inhabits the tubes of terebellid polychaetes near mangrove roots. It can be distinguished from the type species from Guam, Gustavus mecognathus Ahyong & Ng, 2009, by the structure of the dorsal surface of the carapace, the proportions and form of the frontal margin, the shape of the third maxilliped, the armature of the basis-ischium and merus of the third and fourth ambulatory legs, and the structure of the male pleon and gonopods.