The new species Cucumis omissus Thulin from Yemen, Oman and Ethiopia is described and illustrated. According to phylogenetic analyses based mainly on nuclear ribosomal ITS sequences and chloroplast trnG sequences, the new species is sister to C. hastatus in Somalia and Ethiopia. A map showing the distributions of both C. omissus and C. hastatus is provided and morphological differences between these two species are pointed out. Cucumis omissus has been confused with C. pustulatus and C. prophetarum in the literature and in herbaria, and morphological differences from these two species are provided as well. Oreosyce africana is nested within Cucumis in this, as well as in several previous studies. We clarify that when O. africana is treated as a Cucumis, its correct name is C. subsericeus.