Gymnoxenisthmus tigrellus is described from the 15.2 mm SL holotype collected from the Farasan Archipelago, southern Red Sea. It is distinguished from other xenisthmid genera in having the following combination of characters: head pores absent; no scales; first dorsal fin with five spines; at least some dorsal-, anal- and pectoral-fin rays branched; pelvic fin with a spine and five unbranched rays. Evaluation of available (mostly external) characters suggests the new genus is the sister group of a clade consisting of Rotuma, Tyson and Allomicrodesmus.