Quraysh decided to rebuild the Ka'ba when the prophet was thirty-five years of age. They were planning to roof it and feared to demolish it, for it was made of loose stones above a man’s height.

A ship belonging to a Roman merchant had been cast ashore at Judda and became a total wreck. They took its timbers and got them ready to roof the Ka'ba. It happened that in Mecca there was a Copt who was a carpenter, so everything they needed was ready to hand. A snake used to come out of the well in which the sacred offerings were thrown and sun itself every day on the wall of the Ka ba. It was an object of terror because whenever anyone came near it it raised its head and made a rustling noise and opened its mouth, so that they were terrified of it. While it was thus sunning itself one day, Allah sent a bird which seized it and flew off with it. Thereupon Quraysh said, ‘Now we may hope that Allah is pleased with what we intend to do. We have a friendly craftsman, we have got the wood and Allah has rid us of the snake.’ When they had decided to pull it down and rebuild it Abu Wahb ibn 'Amr b. 'A’idh ibn 'Abd ibn 'Imran ibn Makhzum got up and took a stone from the Ka'ba and it leapt out of his hand so that it returned to its place. He said, "O Quraysh, do not bring into this building ill-gotten gains, the hire of a harlot, nor money taken in usury, nor anything resulting from wrong and violence"

Then Quraysh divided the work among them; the section near the door was assigned to Banu 'Abdu Manaf and Zuhra. The space between the black stone and the southern corner, to Banu Makhzum and the Qurayshite tribes which were attached to them. The back of the Ka'ba to Banu Jumah and Sahm. The side of the hijr to Banu 'Abdud-Dar ibn Qusayy and to Banu Asad bin Abdul-'Uzza and to Banu 'Adiy ibn Ka'b.

The people were afraid to demolish the temple, and withdrew in awe from it. Al-Walld bin al-Mughlra said, ‘I will begin the demolition.’ So he took a pick-axe, went up to it saying the while, ‘O Allah, we have not disbelieved (in your religion), we intend only what is best.’ Then he demolished the part at the two corners. That night the people watched, saying, ‘We will look out; if he is injured we won’t destroy any more of it and will restore it as it was; but if nothing happens to him then Allah is pleased with what we are doing and we will demolish it.’ In the morning al-Walid returned to the work of demolition and the people worked with him, until they got down to the foundation of Abraham (AS), they found green stones like camel’s humps joined one to another.

The tribes of Quraysh kept on gathering stones for the building, each tribe collecting them and building by itself until the building was finished up to the black stone, where controversy arose, each tribe wanting to lift it to its place, until they went their several ways, formed alliances, and got ready for battle.

A narrator said that Abu Umayya who was at that time the oldest man of Quraysh, urged them to make the first man to enter the gate of the mosque arbitrate the matter in dispute. They did so and the first to come in was the prophet of Allah (SAS). When they saw him they said, ‘This is the trustworthy one (Al-Amin). We are satisfied! This is Muhammad.’ When he came to them and they informed him of the matter he said, ‘Give me a cloak,’ and when it was brought to him he took the black stone and put it inside it and said that each tribe should take hold of an end of the cloak and they should lift it together. They did this so that when they got it into position he placed it with his own hand, and then building went on above it.