The land chosen for the masjid belonged to two orphan boys, who donated the land. Aa’ishah (ra) said: “Allah’s Messenger (saw) mounted his riding beast and knelt at the site of his osqu and the place where it knelt was a resting place belonging to Sahl and Suhail, two orphan boys in the care of As’ad bin Zurarah; and when his mount knelt, Allah’s messenger (saw) said: ‘This, Allah willing, is the place where it has stopped.’  Then he called the two orphan boys and he haggled with them over the price of the land, in order to take it for the mosque, but they said: ‘No, we will donate it to you, Oh Messenger of Allah!’  Then he had the mosque built on it and he began to move the bricks with them for the building of it, and he said: “This (carrying) work is not the work of Khaibar. This is more pious, Oh our lord and purer.”

And he said: “Oh Allah! The reward is the reward of the Hereafter, so show mercy to the Ansar and the Muhajirun.” [Al Bukhary]

The original mosque was built by Muhammad next to the house where he settled after his journey to Medina in 622 AD. The original mosque was an open-air building with a raised platform for the reading of the Qur’an. It was a rectangular enclosure of 30 × 35 m (98 × 115 ft), built with palm trunks and mud walls, and accessed through three doors: Bab Rahmah (Door of Mercy) to the south, Bab Jibril (Door of Gabriel) to the west and Bab al-Nisa’ (Door of the Women) to the east.

The basic plan of the building has since been adopted in the building of other mosques throughout the world. [wikipedia]

Nafi (ra) said that Abdullah bin Umar (ra) told him that in the time of the Messenger (saw), the mosque was built from adobe bricks and its roof was made from date-palm branches and its pillars were the trunks of date-palm trees. {Al Bukhary]

The Prophet (saw) use to stand by one of the trunks, and so an Ansar woman suggested they make him a pulpit.  Jabir bin Abdullah (ra) reported that on Fridays, the prophet (saw) used to stand by a tree, or a date-palm and a woman or a man from the Ansar said: “Oh Messenger of Allah! Shall we not make for you a pulpit?”  And he (saw) said: “if you wish”. So they made a pulpit for him, then when Friday came, he ascended the pulpit and the date palm cried out like the crying of a child. Then the prophet (saw) descended and embraced it and it began to moan like the moaning of a child which has been quieted and he said: “It was crying because of the dhikr which it used to hear next to it.” [Al Bukhary]

The pulpit of the Prophet (saw) has a high status. The Messenger (saw) said: “What lies between my house and my pulpit is a garden from among the Gardens of paradise and my pulpit is over my pool (al Kauthar)” [Al Bukhary and Al Muslim]

The mosque was expanded several times over the next few decades. The land for the first expansion was purchased, and donated by Uthman bin Affan (ra). After the Prophet’s (saw) return from the battle of khaibar, the number of Muslims had increased significantly, and so the length of the mosque was increased by thirty cubits and the width by thirty cubits. The foundations were made from stone.

1. During the caliphate of Abu Bakr (ra), some of the columns (made from date-pine tree tunks) had worn out, so they were replaced.

2. During the caliphate of Umar bin Al Khattab (ra), 17AH, the number of Muslims had increased considerably, and so the people asked Umar (ra) to increase the size of the mosque. The mosque was extended and the roof was raised. Mujahid (ra) said: “Its pillars were made from date-palm wood and Abu Bakr (ra) did not add anything to it, but Umar (ra) extended it and rebuilt it in the same manner in which it was built during the time of Allah’s Messenger (saw), of adobe bricks and date-palm branches and he replaced its pillers with wood.” [Ahmad and Abu Dawud]

Umar (ra) also added a platform on the Western side, called Al Butaiha’, for those people who wanted gossip, raise voices, etc.

3. During the caliphate of Uthman bin Affan (ra), 29AH, the mosque was once again extended, increasing it from the direction of Qiblah, from the North and the West. He added a cloister, placing its wall on the side of the Qiblha, and adding a cloister to the Western side.  At present, the imam leads the salah from the same place Uthman (ra) did.

Al Muttalib bin Abdullah bin Hantab said: “ When Uthman bin Affan came to power in the year 24 AH, the people spoke to him about increasing the size of their mosque and they complained to him about  its narrowness on Fridays, to the extent that they prayed in the open outside the mosque, so Uthman (ra) consulted the sound judgment among the companions of Allah’s Messenger (saw) and  they agreed that he should demolish it and extend it, so he performed the dhohr pray with the people, then he mounted the pulpit and praised and thanked Allah and extolled Him and then he said: “Oh you people! I wish to demolish the mosque of Allah’s Messenger (saw) and then extend it and I testify that I heard Allah’s messenger (saw) saying: ‘Whoever built a mosque for Allah’s sake, Allah will build him a house in Paradise.’ And there is a precedent for me to do this and an imam who preceded me: ‘Umar bin Al Khattab, for he extended it and rebuilt it and I have consulted those of sound judgement among the companions of Allah’s Messenger (saw) and they have agreed that it should be demolished and rebuilt and expanded,”

4. During the time of Al Waleed bin Abdul Malik, the governor of Madinah, Umar bin Abdul Aziz, was ordered to rebuild and expand the mosque. This took place in 88AH and finished in the year 91AH.  Umar bin Abdul Aziz bought the huts of the wives of the Prophet (saw), and incorporated them in the mosque. Two ceilings were made, the upper one, to protect the lower one from any damage caused by the weather.  The North, West and East side were increased. The pillars were made from Iron and lead. Marble slabs were placed on the internal walls, as well as some gold and mosaic. Umar bin Al Waleed was the first person to add minarets to the building. The new mosque now had 20 doors.

5. During the time of Al Mahdi, the Abbasid ruler, in the year 161AH, Al Mahdi performed Hajj and then appointed Jafar bin Sulayman as governor and told him to expand the Prophet’s (saw) mosque.  Abdullah bin Asim bin Umar bin Abdul Aziz, was helping in supervising the construction.  Some of the houses of the companions were bought and included in the expansion, of them were the houses of Abdurrahman bin Auf (ra) and Shurabil bin Hasanah (ra), and parts of Abdullah bin Mas’ud (ra).

At the end of the Abbassid rule, the Egyptian kings took over the responsibility of the Prophet’s (saw) holy mosque in the year 656AH.

6. During the rein of Sultan Quaitbay, in Ramadan 886AH, lightning struck the minaret, and it caught fire. Sultan Quaitbay undertook the responsibility of restoring the mosque. Only one roof was made and the eastern side was extended. The completion of restoration, took place in the year 888AH. The holy mosque remained as it was for three hundred and seventy years.

7. After the Quaitbay rule ended, the Ottomans took over the responsibility of the Prophet’s (saw) holy mosque in the year 923AH. Madinah was now ruled by Sultan Abdul Majeed. The mosque was showing disrepair, so the imam, Daqood Pasha, wrote to the sultan to tell him that the mosque needed remodeling. Thus Sultan Abdul Majeed sent two engineers, Ramzi Afandi and Uthman Afandi to design the mosque. They returned to the sultan with requirements and plan of the remodeling. The remodeling started in the year 1265AH, and was supervised by Halim Afandi. The entire mosque was remodeled with the exception of the three mihrabs (the Prophet’s (saw), Uthman’s (ra), and Sulayman’s (ra)) the main minaret.

Red rock was found from one of the surrounding mountains, and this was used in the construction. The domes were decorated with Qur’anic verses. The verses were written by Abdullah Zuhdi Afandi, who was a well known calligrapher during that time.  The whole floor and parts of the qiblah wall, were covered in marble. To distinguish Ar Rawdah, they added white and red marble to the pillars. Another door, Al bab al majeedi was added. The remodeling took three years to complete.

8. The first Saudi extension (1368AH) was started by king Abdul Aziz and completed by Kind Saud bin Abdul Aziz. The prophet’s (saw) mosque had five minarets, three of which were removed. The Saudi government built two more minarets in the eastern and western corners, which totaled four minarets. A library was built along the western wall to house historic Qur’ans and other religious texts. On the eastern side, there were three galleries, and a further three galleries, across the courtyard. The door, bab al Malik Abdul Aziz was opened. On the northern side of the courtyard, there were five galleries. The expansion cost 50 million riyals. The mosque was able to hold 28000 worshippers.

Due to the increased number of pilgrims, king Faisal had shelters built, covering an area of 35 thousand square feet. These shelters had lights, fans.

9. The second Saudi extension (1405AH) was started by king Fahd bin Abdul Aziz, the custodian of the two holy mosques. This was the largest expansion to ever take place. He himself laid the foundation stone near bab salam with verses from the Qur’an, Surah An Nur: 36. Six new minarets were built, as well as movable domes, for natural light and ventilation. The dome has patterns that are carved by hand, and has gold work on it. The extension was completed in the year 1414AH.  The mosque was now able to hold a staggering 268000 worshippers inside the mosque, and another 430000 in the open area surrounding the mosque. In the open area, are toilets, ablution areas, and escalators connecting to the underground car park. There are umbrellas in the open area that open up during the day when the weather is at its peak. This is to give shade to the worshippers.