Hysterothylacium aduncum (Nematoda, Anisakidae) was isolated from the intestine of the common sole Solea solea (Family, Soleidae) collected from coasts along Alexandria City at the Mediterranean Sea in Egypt, during the period from May to September 2013. Light and scanning electron microscopy revealed that this nematode parasite belongs to the family Anisakidae in the genus Hysterothylacium. The type species is named H. aduncum, based on the presence of three interlocked lips with the interlabium in between, the presence of cephalic papillae, and large numbers of caudal papillae in males. Body measurements showed that the male worms were smaller than females measuring 13.9-18 mm (16.2 ± 0.2) in length and 0.26-0.34 mm (0.30 ± 0.01) in width. Females measured 20.5-24.5 mm (22.7 ± 0.2) in length and 0.41-0.52 mm (0.45 ± 0.01) in width. The morphological characteristics of this species was confirmed by molecular analysis of 18S rDNA for these parasites followed by comparison between sequence data for them with those obtained from the Genbank showing that H. aduncum is deeply embedded in the genus Hysterothylacium with a sequence similarity between 95.5-94.3 % with close relationships to other H. aduncum specimens and Hysterothylacium sp.. Furthermore, it was shown that this parasitic nematode is able to accumulate larger concentrations of heavy metals such as Fe, Cu, Cd, and Ni within its tissues than of its host fish and thus it can be used as a useful bio-indicator of water pollution.