The present study is based on specimens collected in coffee orchards on the mountains in the Jazan Province (southwestern Saudi Arabia) using Malaise traps. The genera Carinostigmus Tsuneki, 1954, and Polemistus de Saussure, 1892 are first recorded for the Arabian Peninsula, each with a single species. Three new species: Bembecinus similis Gadallah & Edmardash, Crossocerus arabicus Gadallah & Edmardash, and Oxybelus coffeae Edmardash & Gadallah are described and illustrated. The previously unknown female of Nysson ohli (Schmid-Egger 2011) (UAE) is discovered, described and illustrated.