Petra, Yunanca "taş" anlamına gelen "petra" kelimesinden türetilmiştir. Ancak, Petra'nın adı farklı kaynaklarda çeşitli şekillerde de anılmıştır: Amarna mektuplarında Petra, "Pel", "Saleh" (Kaya) veya "Seir" olarak geçmektedir. Yahudi tarihçi Josephus ise bölgeye Musa zamanında Medyanlılarca yerleşildiğini ve bu beş kraldan birinin adının Rekem olduğunu yazmıştır. İslam tarihi araştırmacısı Dan Gibson ise şehrin Arapça adının "Bakka" (veya "bekke") olduğunu öne sürmüştür. Ayrıca, kayalara oyulmuş yapılarının renginden dolayı Petra, "gül kırmızısı şehir" olarak da bilinir.