In tempi antichi la città era abitata da Thamudeni e Nabatei, ed era conosciuta con il nome di Hegra. Fu occupata da legionari romani durante l'espansione di Traiano nel Vicino Oriente, nel secondo secolo d.C.

Alcune delle iscrizioni rinvenute in questo luogo sono state datate al I millennio a.C. Tutti gli altri elementi architetturali risalgono invece al periodo dei Thamudeni e dei Nabatei, tra il II secolo a.C. ed i II secolo d.C.[1]

«Tra il caldo e la foschia, in due ore di marcia sulla friabile piana sabbiosa raggiungemmo Medain Salih, secondo markaz o stazione di riposo sul percorso, a metà del lungo viaggio per la Mecca. L'arrivo della carovana fu accolto da molti colpi dei pezzi da campo, dopo di che smontammo al nostro accampamento di tende bianche, piantate un po' prima della qalaa»

(Charles Montagu Doughty[2])

Recentemente sono state scoperte evidenze dell'occupazione romana ai tempi di Traiano e forse di Adriano: l'area montuosa di Hijaz nell'Arabia nordoccidentale probabilmente era parzialmente fertile e fece parte della provincia romana dell'Arabia Petrea con capitale Petra[3]

Nel 2008, l'UNESCO ha iscritto Madāʾin Ṣāliḥ tra i patrimoni dell'umanità, rendendolo il primo patrimonio riconosciuto dell'Arabia Saudita.[4]