Majma al-Zawaid — Hadith 5729

Sayyiduna Abu al-Tufayl (may Allah be pleased with him) narrates: In the time of Jahiliyyah the Ka'bah was built of loose stones, and it was so low that a young goat could climb onto it. It had no roof; cloths were placed upon it and then let hang down. The Black Stone was placed on its wall, and it was in the shape of a ring with two corners. A ship was coming from the land of the Romans; when it came near Jeddah, the ship broke apart. Quraysh went out to obtain its wood. They found a Roman man by it; Quraysh took the wood, which he gave to them. The ship had been heading for Abyssinia, and the Roman man who was on the ship was a carpenter. When Quraysh returned, they brought the Roman back with them. Quraysh said: "We will build the House of our Lord with this wood that was in the ship." When they intended to demolish the Ka'bah, there was a snake on the wall of the Ka'bah, like a weak thing, with a black back and a white belly. Whenever anyone wanted to approach the House to demolish it, or wanted to take down one of its stones, the snake would rush at him with its mouth open. Quraysh gathered at the Maqam of Ibrahim. They implored Allah Almighty with weeping and said: "O our Lord, our only aim is to honour Your House and to adorn and beautify it. If You are pleased with this, then do whatever seems good to You." Then they heard a sound in the sky, and there was a bird with a black back and a white belly, which had two feet; it was larger than a human. It sank its talons into the snake's head and went off with it; the snake's tail was bigger than such-and-such a thing. It went off towards Ajnad. Quraysh demolished the Ka'bah and then began to build it with the stones of the valley; Quraysh would carry those stones on their necks. They raised it twenty cubits high. The Prophet (peace and blessings be upon him) too used to carry stones from Ajnad. He was wearing a sheet, and the sheet was small. He wanted to put the sheet on his shoulder, and because the sheet was small his private parts became exposed. Then it was called out: "O Muhammad! Cover your private parts." After that the Prophet (peace and blessings be upon him) was never seen naked. Between this construction of the Ka'bah and the revelation coming down upon the Prophet (peace and blessings be upon him) there were five years, and between the Prophet (peace and blessings be upon him)'s going out from Makkah and this construction there were fifteen years.
Al-Tabarani recorded it in al-Mu'jam al-Kabir as a long narration, and Ahmad recorded a part of it; the narrators of both are the narrators of the Sahih.