Mayfly larvae and imagos were collected at approximately 50 localities of the Kingdom of Saudi Arabia (KSU). Included in this material, three species of <i>Labiobaetis</i> Novikova & Kluge, 1987 are recorded, two of them being new to science. <i>Labiobaetis potamoticus</i> Gattolliat & Al Dhafer, <b>sp. n.</b> is described from both larvae and adults, whereas <i>Labiobaetis alahmadii</i> Gattolliat & Al Dhafer, <b>sp. n.</b> is only known from the larval stage. The two species are compared morphologically with Palearctic and Afrotropical species of <i>Labiobaetis</i> . A third species, <i>Labiobaetis glaucus</i> (Agnew, 1961) is reported for the first time from the Arabian Peninsula. The species was originally described from South Africa and subsequently reported from the east and northeast of Africa. A molecular reconstruction including 18 Afrotropical and Palearctic species of <i>Labiobaetis</i> was performed using 658 bp of the mitochondrial gene CO1. The reconstruction highly supported the validity of the two new species and confirmed the occurrence of <i>L. glaucus</i> in KSU.