The province, a part of the Diocese of the East, was split from Arabia Petraea during the reforms of Diocletian in c.300 CE[1] and existed until the Muslim Arab conquests of the 7th century.

[2] Petra declined rapidly under late Roman rule, in large part from the revision of sea-based trade routes.

[3] The area became organized under the late Roman Empire as part of the Diocese of the East (314), in which it was included together with the provinces of Isauria, Cilicia, Cyprus (until 536), Euphratensis, Mesopotamia, Osroene, Phoenice and Arabia Petraea.

Palaestina Tertia included the Negev, southern Transjordan, once part of Arabia Petraea, and most of Sinai.

[4]: 8 [5] According to historian H. H. Ben-Sasson,[6]: 351 The Muslim Arabs found the remnants of the Nabataeans of Transjordan and the Negev transformed into peasants.