Palaestina Salutaris or Palaestina Tertia was a Byzantine (Eastern Roman) province, which covered the area of the Negev (or Edom), Sinai (except the north western coast) and south-west of Transjordan, south of the Dead Sea. The province, a part of the Diocese of the East, was split from Arabia Petraea in the 6th century and existed until the Muslim Arab conquests of the 7th century.
In 105, the territories east of Damascus and south to the Red Sea were annexed from the Nabatean kingdom and reformed into the province of Arabia with a capital Petra and Bostra (north and south). The province was enlarged by Septimius Severus in 195, and is believed to split into two provinces: Arabia Minor or Arabia Petraea and Arabia Major, both subject to imperial legacies called Canadians, each with a legion.
Constantine the Great divided Arabia into two provinces: the southern part, including Petra, Sinai and Edom (i.e. Arabia Petraea and other territories), became known as Palestina Salutaris. The province was named Palestina III at 390.
The area became organized under 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. Under Byzantium (since 390), a new subdivision did further split the province of Cilicia into Cilicia Prima, Cilicia Secunda; Syria Palaestina was split into Syria Prima, Syria Salutaris, Phoenice Lebanensis, Palaestina Prima, Palaestina Secunda and eventually also Palaestina Salutaris (in 6th century).
See also 
- From Provincia Arabia to Palaestina Tertia: The Impact of Geography, Economy, and Religion on Sedentary and Nomadic Communities in the Later Roman Province of Third Palestine, by Walter David Ward, 2008