The original description of the genus Tetragonocephalum was published more than one hundred years ago but its taxonomic status was clarified only recently. To date, approximately 30 nominal species of this genus have been described, mostly from the northern Indian Ocean, but nearly half of them are invalid and only 14 species are recognized as valid. In the present study two new species of Tetragonocephalum are described from the spiral intestine of Himantura randalli from off Jod, on the northern coast of the Gulf of Oman. Tetragonocephalum sabae sp. n. is distinguishable from the valid species of Tetragonocephalum based on number of proglottids (43−53), number of testes (42−50), and size of scolex (401−453×328−455), acetabula (87−109×72−116), mature proglottids (802−1,333×226−336), cirrus sac (92−160×103−154), and eggs (16−19×11−13). Tetragonocephalum salarii sp. n. can be distinguished from T. sabae sp. n. and all other valid species of Tetragonocephalum based on number of proglottids (77−86). Furthermore, it differs from its congeners based on a combination of some characteristics, including the number of mature (3−7) and gravid (18−20) proglottids, the number of testes (30−38), and the size of acetabula (84−111×80−96), mature proglottids (497−833×334−403), gravid proglottids (1,036−1,482×440−575), testes (20−34×31−50), ovary (123−215×210−278), and eggs (24−45×13−21).