The plant parasite Hydnora arabica (Aristolochiaceae) is described from the Arabian Peninsula. This species was previously identified as Hydnora africana in Oman. It can be separated from other Hydnora taxa primarily by its terete rhizome, red to orange inner perianth tube color, and tepal lobe margins entirely covered with dense strigose setae. In Oman, Hydnora arabica is known to parasitize two leguminous trees: Acacia tortilis and the introduced Pithocellobium dulce, but may parasitize additional Fabaceae. At least eleven synonyms or subspecific varieties of H. abyssinica are described in the literature, all from east or southern Africa. These synonyms are discussed in light of new observations of morphology including tepal margin ornamentation. A new key for Hydnora is proposed.