Four previously unrecognized trypanorhynchids are described based on fish specimens from Sparidae and Mullidae host fish of the Red Sea. From September 2010 to June 2011, 66 specimens of the sea bream Pagrus pagrus (F: Sparidae) and 43 of the red mullet Mullus barbatus (F: Mullidae) were purchased from markets in the Suez and Hurghada cities of the Red Sea. The fishes were measured, and their organs investigated for helminth infections. Forty-one (37.6 %) out of the 109 fish specimens investigated were parasitized with Trypanorhyncha metacestodes, identified as Callitetrarhynchus speciouses Linton 1897, Pseudogrillotia sp. Dollfus 1969, Kotorella pronosoma Stossich 1901 from P. pagrus, and Nybelinia bisulcata Linton 1889 from M. barbatus in the mesentery and peritoneal cavity, with prevalences of 16.5, 11.0, 6.0, and 12.0 %. All of these larval stages were encapsulated larvae in blastocysts. C. speciouses is characterized by an elongated scolex, two bothria, a long postbulbosa, and four elongated bulbs. Pseudogrillotia sp. possesses a scolex with two lateral patelliform bothridia; posterior margins are free, not notched. A long sheath was observed, which was irregularly coiled when tentacles invaginated. N. bisulcata possesses an acraspedote scolex with four bothridia, which are broad, bean-shaped. The tentacles are spirally coiled, supplied with hooks with abruptly turned points. The four tentacles sheaths rose from scolex as two anterior (front) and two posterior (back) which overlap at the apices of bulbs. K. pronosoma is characterized by a short body with a craspedote scolex and four bothridia. The tentacles are short and emerge pairwise. The presence of Trypanorhyncha metacestodes in the muscles does not represent a risk of infection for humans. They have a negative effect on fish esthetics. The repugnant aspect and the prohibition for commercial use by sanitary inspectors, however, cause consumer rejection. Parasites of the order Trypanorhyncha have been recorded in these host fishes for the first time.