A revision of the rhinocerotid material from the Negev (Israel), dating back to the early Miocene (MN3 in the European Mammal Biochronology), highlights the presence of Brachypotherium and a taxon close to Gaindatherium in the Levantine Corridor. A juvenile mandible, investigated using CT scanning, displays morphologically distinct characters consistent with B. cf. B. snowi rather than with other Eurasian representatives of this genus. Some postcranial remains from the Negev, such as a humerus, display features that distinguish it among Miocene taxa. We attribute these postcrania to cf. Gaindatherium sp., a taxon never recorded outside the Siwaliks until now. This taxon dispersed into the Levantine region during the late early Miocene following a pattern similar to other South Asian taxa. Brachypotherium cf. B. snowi probably occurred in the Levantine region and then in North Africa during the early Miocene, as its remains are known from slightly younger localities such as Moghara (Egypt) and Jebel Zelten (Libya). The occurrence cf. Gaindatherium sp. represents a previously unrecorded range expansion out of Southeast Asia. These new records demonstrate the paleogeographic importance of the Levantine region showcasing the complex role of the Levantine corridor in intercontinental dispersals between Asia and Europe as well as Eurasia and Africa.