By 7000 BC, some of the earliest recorded farmers had settled in Beidha, a pre-pottery settlement just north of Petra. Petra is listed in Egyptian campaign accounts and the Amarna 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).
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 elaborate faç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 of Aretas IV Philopatris, (9 BC–40 AD), the tombs of the el-I~ejr type may be dated, and perhaps also the High-place.

In 106 AD, when Cornelius Palma was governor of Syria, the part of Arabia under the rule of Petra was absorbed into the Roman Empire as part of Arabia Petraea and became its capital. The native dynasty came to an end but the city continued to flourish under Roman rule. It was around this time that the Petra Roman Road was built. A century later, in the time of Alexander Severus, when the city was at the height of its splendor, the issue of coinage comes to an end. There is no more building of sumptuous tombs, owing apparently to some sudden catastrophe, such as an invasion by the neo-Persian power under the Sassanid Empire. Meanwhile, as Palmyra (fl. 130–270) grew in importance and attracted the Arabian trade away from Petra, the latter declined. It appears, however, to have lingered on as a religious centre. Another Roman road was constructed at the site. Epiphanius of Salamis (c.315–403) writes that in his time a feast was held there on December 25 in honor of the virgin Khaabou (Chaabou) and her offspring Dushara (Haer. 51).