Petra is listed in Egyptian campaign accounts and theAmarna letters as Pel, Sela or Seir. Though the city was founded relatively late, a sanctuary has existed there since very ancient times. Stations 19 through 26 of the stations list of Exodus are places associated with Petra. This part of the country was biblically assigned to the Horites, the predecessors of the Edomites. The habits of the original natives may have influenced the Nabataean custom of burying the dead and offering worship in half-excavated caves. Although Petra is usually identified with Sela, which means a rock, the Biblical references refer to it as "the cleft in the rock", referring to its entrance. In the parallel passage, however, Sela is understood to mean simply "the rock" (2 Chronicles xxv. 12, see LXX).
Josephus (Antiquities of the Jews iv. 7, 1~ 4, 7), Eusebius and Jerome (Onom. sacr. 286, 71. 145, 9; 228, 55. 287, 94) assert that Rekem was the native name, and this name appears in the Dead Sea Scrolls as a prominent Edomite site most closely describing Petra, and associated with Mount Seir. But in the Aramaic versions, Rekem is the name of Kadesh, implying that Josephus may have confused the two places. The Semitic name of the city, if not Sela, remains unknown. The passage in Diodorus Siculus (xix. 94–97) which describes the expeditions which Antigonus sent against the Nabataeans in 312 BC is understood to throw some light upon the history of Petra, but the "petra" referred to as a natural fortress and place of refuge cannot be a proper name and the description implies that the town was not yet in existence.
Rekem is likely derived from the Nabataean name for the city, Raqmu.
The name "Rekem" was inscribed in the rock wall of the Wadi Musa opposite the entrance to the Siq, However, Jordan built a bridge over the wadi and this inscription was buried beneath tons of concrete.
More satisfactory evidence of the date of the earliest Nabataean settlement may be obtained from an examination of the tombs. Two types of tombs have been distinguished: the Nabataean and the Greco-Roman. The Nabataean type starts from the simple pylon-tomb with a door set in a tower crowned by a parapet ornament, in imitation of the front of a dwelling-house. Then, after passing through various stages, the full Nabataean type is reached, retaining all the native features and at the same time exhibiting characteristics which are partly Egyptian and partly Greek. Of this type close parallels exist in the tomb-towers at Mada'in Saleh in north Arabia, which bear long Nabataean inscriptions and supply a date for the corresponding monuments at Petra. Then comes a series of tombfronts which terminate in a semicircular arch, a feature derived from north Syria. Finally come the elaboratefaçades copied from the front of a Roman temple; however, all traces of native style have vanished. The exact dates of the stages in this development cannot be fixed. Few inscriptions of any length have been found at Petra, perhaps because they have perished with the stucco or cement which was used upon many of the buildings. The simple pylon-tombs which belong to the pre-Hellenic age serve as evidence for the earliest period. It is not known how far back in this stage the Nabataean settlement goes, but it does not go back farther than the 6th century BC. A period follows in which the dominant civilization combines Greek, Egyptian and Syrian elements, clearly pointing to the age of the Ptolemies. Towards the close of the 2nd century BC, when the Ptolemaic and Seleucid kingdoms were equally depressed, the Nabataean kingdom came to the front. Under Aretas III Philhellene, (c.85–60 BC), the royal coins begin. The theatre was probably excavated at that time, and Petra must have assumed the aspect of a Hellenistic city. In the reign ofAretas IV Philopatris, (9 BC–40 AD), the tombs of the el-I~ejr[clarification needed] type may be dated, and perhaps also the High-place.