History of Hajj
Question

I would like you to tell me about the history of Hajj and its rituals. For example, the Muslims perform sa’i, running between al-Safa and al-Marwah, which is what Hajar did. But with regard to the rest, I do not know their origins and I hope that you can tell me – such as the stoning of the Jamarat, tawaf, the standing at ‘Arafah, drinking the water of Zamzam, staying overnight in Mina and Muzdalifah, slaughtering the hadiy (sacrifice), etc.
Praise be to Allah.Hajj: The fifth pillar of Islam
One of the things on which there is scholarly consensus among all the Muslims, ancient and modern, past and present, is that Hajj or pilgrimage to the Sacred House of Allah is one of the five pillars of Islam, as proven in al-Sahihayn from the hadith of Ibn ‘Umar (may Allah be pleased with them both) and others. 
It is well known that Hajj , like other acts of worship, involves special actions, and each of these actions must be done in the prescribed manner, such as entering ihram from the miqat, tawaf, sa’i between al-Safa and al-Marwah, standing in ‘Arafah, staying overnight in Muzdalifah, stoning the Jamarat , slaughtering the sacrifice, and the other well-known actions of Hajj . All of these actions should be done in accordance with the teachings of the Prophet (peace and blessings of Allah be upon him). There are very many ahadith which describe the Hajj of the Prophet (peace and blessings of Allah be upon him); these have been compiled by Imam Ibn al-Qayyim in Zad al-Ma’ad and by al-Hafiz Ibn Kathir in his book al-Bidayah wa’l-Nihayah; these scholars have also explained the rulings derived from these ahadith. The Muslim should pay attention to learning these rulings and acting upon them. 
Purpose of Hajj
Then we should remember that the basic purpose of the actions of Hajj is to establish the remembrance of Allah, as Allah says (interpretation of the meaning):
“Then when you leave ‘Arafat, remember Allah (by glorifying His Praises, i.e. prayers and invocations) at the Mash‘ar-il-Haram. And remember Him (by invoking Allah for all good) as He has guided you, and verily, you were, before, of those who were astray. Then depart from the place whence all the people depart and ask Allah for His forgiveness. Truly, Allah is Oft-Forgiving, Most-Merciful.So when you have accomplished your Manasik [rituals of Hajj], remember Allah as you remember your forefathers or with a far more remembrance. But of mankind there are some who say: ‘Our Lord! Give us (Your Bounties) in this world!’ and for such there will be no portion in the Hereafter…And remember Allah during the appointed Days. But whosoever hastens to leave in two days, there is no sin on him and whosoever stays on, there is no sin on him, if his aim is to do good and obey Allah (fear Him), and know that you will surely be gathered unto Him.” [al-Baqarah 2:198-203]
‘Aishah (may Allah be pleased with her) said: “Tawaf around the House and sa’i between al-Safa and al-Marwah and the stoning of the jamarat were only prescribed so that the remembrance of Allah may be established.” It was classed as mu’allaq by al-Bayhaqi (5/145) and narrated as a marfu’ report, although there is some weakness in it. 
So the Muslim venerates the rituals of Hajj because Allah has commanded him to venerate them, as Allah says (interpretation of the meaning): 
“Thus it is and whosoever honours the Symbols of Allah, then it is truly, from the piety of the hearts.” [al-Hajj 22:32]
Al-Bukhari (1610) narrated that ‘Umar ibn al-Khattab (may Allah be pleased with him) kissed the Black Stone and said, “Were it not that I had seen the Messenger of Allah (peace and blessings of Allah be upon him) kissing you, I would not have kissed you.” 
Actions of Hajj
Ibn al-Jawzi (may Allah have mercy on him) said, whilst discussing and explaining the actions of Hajj :  
“The background to these rituals is no longer present but the rulings remain in effect. These rituals may be confusing for some who see them and do not know the reasons for them, so they may say, ‘This does not make sense.’ I have explained the reasons for them as far as narrated reports go, now I will explain to you the meanings behind them. 
Note that the basis for acts of worship is something rational and comprehensible, which is the submission of the slave to his Lord and obedience to Him. Prayer involves humility and submission, which is what is meant by the word ‘ibadah (worship). 
Zakah involves kindness and helping the poor, so its meaning is clear. 
Fasting means suppressing the desires of the self so that it will be obedient to the One Whom it serves. 
Honouring the House and going there, and establishing a sanctuary (Haram) around it are acts of veneration. Arriving there unkempt and disheveled is like a slave turning to his Lord in humility and submission, and that is clear. A person feels at ease performing rituals that he understands, and that motivates him to do them, but to achieve full submission there are some rituals that a person may not understand, so he will not be at ease and will not comprehend them. In this case the only motive is to obey the commands of Allah. This is a greater form of humility and submission.” (Muthir al-‘Azm al-Sakin (1.285-286). 
History of Hajj
If this is understood, then much of the history of the actions of Hajj before the Messenger (peace and blessings of Allah be upon him) is not known to us. In this case, it does not matter if we do not know. And there are some things concerning whose history a few indications are narrated in some texts; we will mention some of these here: 
When was Hajj enjoined? When did Hajj begin? 
Allah says (interpretation of the meaning): 
“And proclaim to mankind the Hajj (pilgrimage). They will come to you on foot and on every lean camel, they will come from every deep and distant (wide) mountain highway (to perform Hajj).” [al-Hajj 22:27]
Ibn Kathir says in his commentary on this verse (3/221): 
“This means: Proclaim (O Ibrahim) the Hajj to the people, calling them to come on pilgrimage to this House which We have commanded you to build. It was mentioned that he said, “O Lord, how can I proclaim it to the people when my voice does not reach them?” He said, “Call and We will convey it.” So he stood in his maqam (station) – or it was said, on the rock, or on al-Safa, or on Abu Qubays (a mountain) – and said: “O people, your Lord has taken a House, so come to it on pilgrimage.” And it was said that the mountains lowered themselves so that his voice could reach all parts of the earth and those who were still in the wombs or in men’s loins also heard, and everything that heard him, cities, nomad encampments and trees, and everyone whom Allah has decreed should perform Hajj until the Day of Resurrection responded, (saying) Labbayk Allahumma labbayk (Here I am, O Allah, here I am. This is the summary of what was narrated from Ibn 'Abbas, Mujahid, ‘Ikrimah, Sa’id ibn Jubayr and others among the salaf. And Allah knows best.” 
Ibn al-Jawzi, in his book Muthir al-‘Azm al-Sakin (1/354) narrated something similar, but more briefly, and he attributed it to the narrators of Sirah.  
This has to do with the history of the enjoining of Hajj before the sending of the Prophet (peace and blessings of Allah be upon him). 
With regard to the enjoining of Hajj in Islam , there is some scholarly difference of opinion concerning that. It was said that it was enjoined in 6 AH, or in 7 AH, or in 9 AH, or in 10 AH. Imam Ibn al-Qayyim (may Allah have mercy on him) was certain that it was enjoined in 9 or 10 AH. He (may Allah have mercy on him) said in Zad al-Ma’ad:  
“There is no dispute that the Prophet (peace and blessings of Allah be upon him) did not perform Hajj after he migrated to Madinah apart from one Hajj, which was the Farewell Pilgrimage. And there is no dispute that that occurred in 10 AH… When the command to perform Hajj was revealed, the Messenger of Allah (peace and blessings of Allah be upon him) hastened to perform Hajj with no delay. Because the enjoining of Hajj came at a later stage, in 9 or 10 AH, one might say, How can you prove that the command to perform Hajj was delayed until 9 or 10 AH? We would say that the first part of Surah Al ‘Imran was revealed in the year of delegations (‘am al-wufud), during which the delegation from Najran came to the Messenger of Allah (peace and blessings of Allah be upon him) and he made a treaty with them regarding their paying the jizyah, and the (ruling on) jizyah was revealed in the year of Tabuk, 9 AH, when the first part of Surah Al ‘Imran was revealed…” 
Al-Qurtubi said in his Tafsir (2/4/92): Hajj was known to the Arabs. When Islam came, they were told about something they already knew and what was enjoined upon them was something they were familiar with…” See also Ahkam al-Quran by Ibn al-‘Arabi, 1/286. 
Tawaf around the House 
Allah says (interpretation of the meaning): 
“and We commanded Ibrahim (Abraham) and Isma’il (Ishmael) that they should purify My House (the Ka‘bah at Makkah) for those who are circumambulating it, or staying (I‘tikâf), or bowing or prostrating themselves (there, in prayer).” [al-Baqarah 2:125]
This verse indicates that tawaf around the Ka’bah was known at the time of Ibrahim (peace be upon him). 
Raml 
Raml means walking quickly with short steps. This is Sunnah for men but not for women during the tawaf of arrival (tawaf al-qudum), which is the first tawaf performed when one arrives in Makkah. 
How did raml begin? 
Al-Bukhari narrated in his Sahih (2/469-470, 1602) and Muslim also narrated (2/991-992, 1262) that Ibn ‘Abbas (may Allah be pleased with him) said: The Messenger of Allah (peace and blessings of Allah be upon him) came with his Companions and the mushrikun said, “There have come to you people who have been weakened by the fever of Yathrib. So the Prophet (peace and blessings of Allah be upon him) commanded them to walk quickly (raml) in the first three circuits… According to another report, he said, “Walk quickly so that the mushrikin will see that you are strong.” 
The water of Zamzam and sa’i between al-Safa and al-Marwah 
Al-Bukhari narrated in his Sahih (6/396-397, 3364) that Ibn 'Abbas (may Allah be pleased with him) said:  
“Ibrahim brought Hajar and her son Isma’il when she was still breastfeeding him, to a place near the Ka’bah under a tree on the spot of Zamzam, at the highest place in the mosque. During those days there was nobody in Makkah, nor was there any water. So he left them there and left with them a leather bag containing some dates, and a small water-skin containing some water, and set out homeward. Isma’il’s mother followed him saying, “O Ibrahim! Where are you going, leaving us in this valley where there is no person whose company we may enjoy, nor is there anything (to enjoy)?” She repeated that to him many times, but he did not look at her. Then she asked him, “Has Allah commanded you to do this?” He said, “Yes.” She said, “Then He will not forsake us,” and went back while Abraham proceeded onwards. When he reached al-Thaniyah where they could not see him, he turned to face the Ka’bah, and raising both hands, invoked Allah saying the following prayer:  
“O our Lord! I have made some of my offspring to dwell in an uncultivable valley by Your Sacred House (the Ka‘bah at Makkah) in order, O our Lord, that they may perform As-Salah (Iqamat-as-Salah). So fill some hearts among men with love towards them, and (O Allah) provide them with fruits so that they may give thanks.” [Ibrahim 14:37]
Isma’il’s mother went on breastfeeding Isma’il and drinking from the water (she had). When the water in the water-skin had all been used up, she became thirsty and her child also became thirsty. She started looking at him (i.e. Isma’il) tossing in agony. She left him, for she could not endure looking at him, and found that the mountain of al-Safa was the nearest mountain to her on that land. She stood on it and started looking at the valley keenly so that she might see somebody, but she could not see anybody. Then she descended from al-Safa and when she reached the valley, she tucked up her robe and ran in the valley like a person in distress and trouble, till she crossed the valley and reached al-Marwah where she stood and started looking, expecting to see somebody, but she could not see anybody. She repeated that (running between al-Safa and al-Marwah) seven times.  
Ibn 'Abbas said: 
“The Prophet (peace and blessings of Allah be upon him) said, “This is the (origin of) the people’s sa’i (walking) between them between them (i.e. al-Safa and al-Marwah).” When she reached al-Marwah (for the last time) she heard a voice and she said to herself “Shh!” and listened attentively. She heard the voice again and said, “O, (whoever you may be)! You have made me hear your voice; have you got something to help me?” Then she saw an angel at the place of Zamzam, digging the earth with his heel (or his wing), until water appeared. She started to make something like a basin around it, using her hand in this way, and started filling her water-skin with water with her hands, and the water was flowing out after she had scooped some of it.” 
Ibn 'Abbas said: 
“The Prophet (peace and blessings of Allah be upon him) said, “May Allah have mercy on the mother of Isma’il! Had she let Zamzam (flow without trying to control it) (or had she not scooped from that water) (to fill her water-skin), Zamzam would have been a stream flowing on the surface of the earth.” And he said: “The angel said to her, ‘Do not be afraid of being neglected, for this is the House of Allah which will be built by this boy and his father, and Allah never neglects His people’…” 
Ibn al-Jawzi said in his book Muthir al-‘Azm al-Sakin (2/47): “This hadith explains the reason why it is called Zamzam, because when the water flowed, Hajar tried to control it (zammat-ha). The linguist Ibn Faris said: Zamzam comes from the words zamamtu al-naqah (I reined in the camel). 
Standing at ‘Arafah 
Abu Dawud and al-Tirmidhi (883) narrated that Yazid ibn Shayban said: 
“We were standing in ‘Arafah in a place far from the mawqif [where the Prophet (peace and blessings of Allah be upon him) stood]. Ibn Mirba’ al-Ansari came to us and said, “I am the messenger of the Messenger of Allah (peace and blessings of Allah be upon him), who says to you: ‘Stay where you are (for it is also the place of standing), for you are standing in the area where your father Ibrahim stood.’” (Classed as sahih by al-Albani in Sahih Abi Dawud, 1688) 
Many of the actions of Hajj stem from the time of Ibrahim (peace be upon him), but the disbelievers introduced some innovations which were not prescribed. When the Prophet (peace and blessings of Allah be upon him) was sent, he opposed them and explained what was prescribed for the actions of Hajj. 
The questioner could also refer to Question no. 3748  for a brief look at the history of al-Masjid al-Haram. 
And Allah knows best.