The Nabataeans built Petra by carving palaces, tombs and monasteries into the stone cliffs in the 3rd century BC.