The Petra Basin, in which the ancient city site rests, was occupied from Neolithic times, but gained its first prominence as a stronghold, and probable capital city, of the biblical Edomites. The towering mountain at the far western side of the basin is today called "Umm Il-Biyara" (The Mother of Cisterns) and is regarded by some as the biblical "Sela," from whose peak King Amaziah reportedly cast down some 10,000 Edomites to their death.

The site name varied between its Greek form, "Petra," and its Arabic form, "RQM," with the former being most commonly found in external records, simply meaning "Rock." The site's identification with the name "RQM" rests upon a passage in Josephus (AJ 4.7.1), where one "Reqemos" is seen as one of the Midianite kings attacking Moses (Numbers 31:8), and to be both king and builder of "Arecem," said to be "...called by the Greeks Petra." The name "Petra" probably referred to Umm Il-Biyara and was used by the Greeks, although some confusion exists in regard to the site name, with RQM sometimes identified with Kadesh-Barnea.

It is possible that the name "RQM" spread as far east as China, since the Shi-Chi , written by Ssu-ma, in late 1st century B.C., reports a present sent to the court of Chang Ch'ien (ca. 120 B.C.) from a site called "Li-Kan." It has been suggested that this was derived from "RQM," i.e., RE > Chinese LI, QEM > Chinese KEM/KAN as a result of oral confusion of M and N, via dialectical change outside of Petra. In mid-3rd and late 5th-century texts, the name "Li-Kan" appears in the Chinese records of Wei-lio and Hou-Lan-Shu, thus bracketing the period relevant to the earthquake of A.D. 363.

After the Roman occupation of the city in A.D. 106, Petra acquired honorific titles as well. In newly recovered documents, the title "Augustocolonia Antoniana Hadriana Metropolis" is to be found, similar to the simpler form, "Petra Hadriana," known in A.D. 131.

By the early 12th century A.D., if not earlier, the site had acquired the name "The Valley of Moses," as a result of relating it to the biblical tradition of the Exodus by early Christian residents, or, a bit later, by the "monks of Saint Aaron." In either case, Christian religious zeal extended Mosaic relationships to all parts of Petra. For example, the Siq (the geologic cleft in the mountain and Petra's main eastern entrance) was seen as the result of Moses' wand striking the rock to bring forth water, a spring just outside of Petra became the "Spring of Moses," and a nearby mountain was named "Jebel Haroun" and was held to be the final resting place of Aaron, the brother of Moses! Those names, and the Mosaic tradition associated with them, were taken over by the Islamic conquerors and have persisted until today!

The Augustan Age urban center of Petra suffered further destruction from later earthquakes and was gradually swallowed by windblown sand. In the stratigraphic record of the "Temple of the Winged Lions," 39 cultural phases have been identified between the great earthquake of A.D. 363 and the modern surface. During this period, five events of temporary occupation occurred between A.D. 363 and another earthquake in A.D. 551, followed by six similar temporary occupations between A.D. 551 and the present.

The geographical location of the ancient site was never really lost, however, since the Christian historian Eusebius, in his volume called Onomasticon, had calculated the distance from Jerusalem to Petra in his documentation of holy places, and the early map of the Roman Empire, known as "Peutinger's Table," also included it as a Roman Empire site in the Middle East.