The genus Oodera Westwood, 1874 (Hymenoptera, Pteromalidae, Cleonyminae) is recorded for the first time for the Arabian Peninsula, from the Kingdom of Saudi Arabia and the Sultanate of Oman. The present study is based on specimens reared from xylophagous beetle larvae of the family Buprestidae (Coleoptera) infesting dead Acacia trees from Al-Dakhiliyah and Dhofar governorates in Oman and Al-Baha, Asir and Riyadh regions in Saudi Arabia. Four new species, Oodera arabica sp. nov., O. omanensis sp. nov., O. rapuzzii sp. nov., and O. similis sp. nov. are described, illustrated and compared with closely related Oodera species. An illustrated key and the xylophagous host records of the species are also provided.