Palaestina Salutaris or Palaestina Tertia is a Byzantine (Eastern Roman) province that covers the area of the Negev (or Edom), Sinai (except the north western coast) and southwest of Transjordan, south of the Dead Sea.

The province, a part of the Diocese of the East, is split from Arabia Petraea in the sixth century and exists until the Muslim Arab conquests of the seventh century.