Allodidymozoon gasterale n. sp. and A. operculare Madhavi, 1982 (Digenea: Didymozoidae) were found encysted in pairs in the stomach wall and head muscles, respectively, of the yellow-finned barracuda Sphyraena obtusata in Kuwait Bay, northern Arabian Gulf. The new species can be distinguished from congeneric species by the site of infection, the arrangement of the two individuals in the cyst, the numbers of ovarian and vitelline terminal branches, the size and shape of testes, and the presence of a seminal receptacle. The two didymozoids were examined under the scanning electron microscope.