The current parasitological study was carried out to investigate helminth parasites infecting the Red spot emperor Lethrinus lentjan inhabiting Hurghada City at the Gulf of Suez, Red Sea, Egypt. Third-stage larvae of nematode parasite was isolated from the intestine as well as body cavity of the examined fish. Light and scanning electron microscopy revealed that this parasite belonged to Anisakidae family within the genus Pseudoterranova. The present species is named Pseudoterranova decipiens based on the presence of triangular mouth aperture with prominent boring teeth and soft swellings of the cuticle, long muscular esophagus, ventrally excretory pore, and narrow transverse slit of anal opening followed by a short mucron. The morphological characteristics of this species were confirmed by molecular analysis of 18S rDNA gene region of the present parasite. It demonstrated a close identity ≥89% with taxa under family Anisakidae, 85% with Raphidascarididae, and 79-84% with Toxocaridae. A preliminary genetic comparison between gene sequence of the present parasite and other oxyurid species placeed it as a putative sister taxon to other Pseudoterranova decipiens described previously. This study demonstrated that the 18S rDNA gene region of Pseudoterranova decipiens yielded a unique sequence that confirmed its taxonomic position in Anisakidae.