The diversity and evolution of the Red Sea invertebrates in mesophotic and deep-water benthic ecosystems remain largely unexplored. The Palaemonidae is a diversified family of caridean shrimps with numerous taxa in need of taxonomic revisions based on recent molecular analyses. The Red Sea mesophotic and bathyal palaemonid shrimps are largely unstudied. During recent expeditions off the Red Sea coast of Saudi Arabia, several palaemonid specimens were collected at a depth range of 88–494 m, spanning the mesophotic and bathyal zones. This material was examined morphologically and genetically to infer phylogenetic relationships among the Red Sea taxa and several other palaemonid genera. The concordant morphological and genetic data led to the description of two new genera and two new species. Moreover, one species was recorded in the Red Sea for the first time, with a new host record, whereas three further deep-water species, which do not occur in the Red Sea, were formally transferred to a different genus. As more exploration efforts are deployed, research on the diversity and evolutionary relationships among marine invertebrates from the Red Sea will further underline the uniqueness of its mesophotic and bathyal fauna.