[[Arab pra-Islam|Bangsa Arab sebelum kedatangan Islam]] adalah pemuja berhala.<ref name=Haykal439>{{cite book |last=Husayn Haykal |first=Muhammad |authorlink=Muhammad Husayn Haykal |title=The Life of Muhammad |url=https://books.google.com/books?id=fOyO-TSo5nEC&pg=PA439 |year=2008 |publisher=Islamic Book Trust |location=[[Selangor]] |isbn=978-983-9154-17-7 |pages=439–40}}</ref> Ka'bah masih menjadi pusat pemujaan mereka, dan dipenuhi dengan berhala dan gambar [[Malaikat]]. Selama musim ziarah tahunan, orang-orang dari dalam dan luar negeri akan mengunjungi Ka'bah.<ref>{{cite book |last= Al Mubarakpuri |first= Safi ur Rahman |chapter=Religions of the Arabs |title=[[Ar-Raheeq Al-Makhtum|The Sealed Nectar: Biography of the Noble Prophet]] |chapter-url=https://books.google.com/books?id=r_80rJHIaOMC&pg=PA45|accessdate= 6 October 2014 |year= 2002 |publisher=Darussalam |isbn=9960-899-55-1 |page=45}}</ref>
Pola Haji saat ini didirikan oleh [[nabi]] [[Islam]] [[Muhammad]] yang melakukan reformasi terhadap ziarah pra-Islam orang-orang Arab pagan pada tahun 632 M,<ref name=EB>{{cite encyclopedia |url= http://www.britannica.com/EBchecked/topic/252050/hajj |title=Hajj |date=2014 |work=Encyclopædia Britannica |access-date=12 August 2014}}</ref> namun asal mula Haji adalah atas perintah [[Tuhan]] kepada [[Ibrahim]] untuk meninggalkan istrinya [[Hagar]] (Hajar) dan anaknya Ismael ([[Isma'il]]) sendirian di padang pasir kuno Mekkah dengan sedikit makanan dan air yang segera berakhir. Mekkah kemudian menjadi tempat yang tidak berpenghuni. Untuk mencari air, HagarHajar dengan putus asa berlari tujuh kali di antara dua [[Shofa dan Marwah|bukit Shofa dan Marwah]] tapi tidak menemukan satu pun.<ref name="Peters4-7">{{cite book |last=Peters |first=F. E. |title= The Hajj: The Muslim Pilgrimage to Mecca and the Holy Places|url= https://books.google.com/books?id=EK5MqskDYC0C&pg=PA4|year=1994 |publisher=[[Princeton University Press]] |location=[[New Jersey]] |isbn= 0-691-02120-1 |pages=4–7}}</ref> Kembali dalam keputusasaan ke di Ismael, dia melihat bayi itu menggaruk tanah dengan kakinya dan keluar air mancur di bawahnya.<ref>{{cite book |last=Haykal |first=Muhammad Husayn |authorlink=Muhammad Husayn Haykal |title=The Life of Muhammad |publisher=The Other Press |url=https://books.google.com/books?id=fOyO-TSo5nEC&pg=29 |year=1994 |page=29 |isbn=9789839154177}}</ref> Karena adanya air, suku-suku mulai menetap di Mekkah, [[Jurhum]] menjadi suku pertama yang datang. Ketika dewasa, Ismail menikah di suku dan mulai tinggal bersama mereka. Quran menyatakan bahwa Ibrahim, bersama dengan anaknya Ismail, membangun fondasi sebuah rumah yang diidentifikasi oleh kebanyakan komentator sebagai Ka'bah. Setelah menempatkan Batu Hitam di sudut timur Ka'bah, Ibrahim menerima sebuah wahyu di mana Allah mengatakan ke di nabi berusia lanjut bahwa dia sekarang harus pergi dan mengumumkan ziarah ke umat manusia. Quran mengacu di kejadian ini dalam Al-Baqarah:124-127 dan Al-Hajj:27-30.<ref group="n">Ayat-ayat tersebut berbunyi: 'Dan ingatlah bahwa Abraham diadili oleh Tuhannya dengan perintah tertentu, yang dia penuhi .... Ingat Kami menjadikan Rumah itu tempat berkumpul untuk pria dan tempat yang aman; Dan bawa kamu stasiun Abraham sebagai tempat sholat; Dan Kami berjanji kepada Abraham dan Ismael, bahwa mereka harus menguduskan rumahku bagi mereka yang menggabungkannya, atau menggunakannya sebagai retret, atau busur, atau sujudlah (di dalamnya dalam doa) .... Dan ingatlah bahwa Abraham dan Ismael mengangkat Dasar-dasar Rumah Tangga (2: 124-127) '' dan '' Dan beritakanlah ziarah di antara manusia: mereka akan mendatangi engkau dengan berjalan kaki dan naik ke atas setiap jenis unta, melalui jalan raya yang jauh dan jauh, supaya mereka dapat Saksikanlah manfaat yang diberikan kepada mereka dan rayakanlah nama Allah, melalui hari-hari yang ditentukan, atas ternak yang telah disediakannya untuk mereka (untuk pengorbanan); maka makanlah daripadanya dan berikanlah kepada yang tertekan itu, orang yang membutuhkan. Kemudian biarlah mereka menyelesaikan upacara yang ditentukan untuk mereka, melakukan sumpah mereka, dan (lagi) mengelilingi Rumah Kuno. (22: 27-29)''</ref> Sesaat sebelum wafatnya, Muhammad melakukan ziarah satu-satunya dan terakhir dengan sejumlah besar pengikut, Dan mengajarkan mereka ritus haji dan tata krama untuk melakukan hal itu. Di dataran [[Arafah]], dia menyampaikan pidato terkenal - yang dikenal dengan [[Perpisahan Khotbah Nabi Muhammad|Khotbah perpisahan Nabi Muhammad]] - ke mereka yang hadir di sana.<ref>{{cite book |last=Peters |first=F. E. |title= The Hajj: The Muslim Pilgrimage to Mecca and the Holy Places |publisher=Princeton University Press |url= https://books.google.com/books?id=EK5MqskDYC0C&pg=PA164|year=1994| page=164 |isbn=9780691026190}}</ref><ref name=Campo283>{{cite encyclopedia |editor=Juan E. Campo |encyclopedia=Encyclopedia of Islam |url=https://books.google.com/books?id=OZbyz_Hr-eIC&lpg=PP1&dq=isbn%3A1438126964&pg=PA283#v=onepage&q&f=false |publisher=[[Facts On File]] |year=2009 |isbn=978-0-8160-5454-1|page=283}}</ref> Sejak saat itu, haji menjadi salah satu dari Lima Rukun Islam.<ref name=Campo494>{{cite encyclopedia |editor=Juan E. Campo |encyclopedia=Encyclopedia of Islam |url=https://books.google.com/books?id=OZbyz_Hr-eIC&lpg=PP1&dq=isbn%3A1438126964&pg=PA494#v=onepage&q&f=false|publisher=[[Facts On File]] |year=2009 |isbn=978-0-8160-5454-1|page=494}}</ref>
Selama [[abad pertengahan]], peziarah akan berkumpul di kota-kota besar seperti [[Basra]], [[Damaskus]], dan [[Kairo]] untuk pergi ke Mekkah dalam kelompok dan karavan yang terdiri dari puluhan ribu peziarah.<ref name="Singer141">{{Citation|first=Amy|last=Singer|title=Constructing Ottoman Beneficence: An Imperial Soup Kitchen in Jerusalem|url=https://books.google.com/books?id=zHBHBTNwBQoC&pg=PA141&dq=Amir+al+hajj+Ottoman&hl=en&sa=X&ei=-ruVVb73G4GbNszmgYgG&ved=0CEQQ6AEwBA#v=onepage&q=Amir%20al%20hajj%20Ottoman&f=false|publisher=SUNY Press|year=2002|isbn=9780791453513|page=141}}</ref><ref name="Philipp102-04">{{Citation|first=Thomas|last=Phillipp|title=The Mamluks in Egyptian Politics and Society|url=https://books.google.com/books?id=WoPF9T4ZiWsC&pg=PA102&dq=Amir+al+hajj&hl=en&sa=X&ei=3ruVVZSAN4mnNp_UgpAE&ved=0CCwQ6AEwAA#v=onepage&q=Amir%20hajj&f=false|publisher=Cambridge University Press|year=1998|isbn=9780521591157|pages=102–104}}</ref>
|