Bu bahsettiğimiz olaylardan, yani Ali’nin aileye katılmasından kısa bir zaman önce, Muhammed (s.a.v.) otuz beş yaşında iken Kureyşliler Kâ’be’yi tekrar inşa etmeye karar verdiler. O zamanlar Kâ’be’nin yüksekliği, bir insan boyu kadardı ve üstünde çatı yoktu. Bu nedenle kapı kilitlense bile hırsızlar kolaylıkla içeri girebilirdi. Kısa bir süre önce, mahzene gömülen hazinelerden bir kısmı çalınmıştı. Ellerinde çatı yapmaya yetecek kadar kereste vardı: Yunanlı bir tüccarın gemisi karaya vurmuştu ve tamir edilemeyecek kadar dağılmış bir halde Cidde kıyısında bekliyordu. Bu nedenle onun kerestelerini çatı yapmak için aldılar. O sırada Mekke’de yetenekli bir marangoz olan bir Kıptî de bulunuyordu.
Fakat Kâ’be’ye duydukları saygı o denli fazla idi ki ona el sürmekte tereddüt ediyorlardı. Plânları, yumuşak ve dayanıksız taşlardan yapılmış olan tüm duvarları yıkıp, yenilerini yapmaktı; fakat kutsal olan bu yeri yıkarak günahkâr olmaktan ve belâya uğramaktan korkuyorlardı. Bu tereddütleri, Kâ’be’nin duvarından her gün güneşlenmek için dışarı çıkan yılanı görmeleriyle daha da arttı. Kim o tarafa yaklaşırsa yılan başını kaldırıyor, dilini çıkarıp tıslıyordu. Bu da onları çok korkutuyordu. Fakat bir gün, yılan güneşlenirken, Allah gökten bir kartal gönderdi; kartal yılanı kaptı ve uçtu gitti. Kureyşliler aralarında şöyle konuştular: “Şimdi Allah’ın bizim niyetimizi tasdik ettiğine inanabiliriz.

Bize yardım edecek bir marangozumuz ve tahtalarımız var, Tanrı bizi yılandan da kurtardı.”
Duvarların üstünden ilk taşı alan, Muhammed (s.a.v.)’in büyük annesi Fâtıma’nın erkek kardeşi Mahzûm’lu Ebû Vehb idi; fakat o taşı alır almaz, taş elinden kurtulup tekrar eski yerine döndü. Bunun üzerine hepsi işe devam etmekten korkarak Kâ’be’den kaçtılar. Daha sonra Mahzûmîlerin reisi, o zaman hayatta olmayan Muğîre’nin oğlu Velîd kazmayı eline aldı. “Yıkım işini sizin yerinize ben yapacağım” dedikten sonra Kâ’be’ye gitti ve şöyle dedi: “Ey Tanrım, korkma! Ey Tanrım biz iyilikten başka birşey istemiyoruz.” Daha sonra Yemen köşesi ile Haceru’l-Esved’in arasındaki güneydoğu duvarının bir kısmını yıktı; fakat diğerleri işe koyulmaktan çekindiler. “Bekleyelim ve görelim” dediler, “Eğer o helâk olursa, Kâ’be’ye dokunmayalım, hatta onu eski haline çevirelim. Fakat eğer o çarpılmazsa, ki bu Allah işimizi onaylıyor demektir, onu sonuna kadar yıkalım.” Gece hiçbir aksilik çıkmadı; Velîd, sabah erkenden tekrar işe başladı, diğerleri de ona katıldılar. Tüm duvarlar, İbrahim’in attığı temellere kadar yıkılınca, yan yana dizilmiş deve hörgüçlerine benzer, büyük, yeşilimsi taşlar ortaya çıktı. Bir adam taşlardan birini çekip çıkarmak için iki taşın arasına bir manivela koydu; fakat ilk hareketinde, tüm Mekke’yi sarsan ve depreme benzeyen bir sallantı oldu. Bunu, temelleri yıkmamaları için yapılan bir uyarı işareti olarak kabul ettiler.
Haceru’l-Esved’in bulunduğu köşede Süryanice bir yazı buldular. Onu, bir Yahudi okuyana dek ne olduğunu bilmeden sakladılar: “Ben Allah’ım ve Bekke’nin Rabbiyim. Bekke’yi, gökleri ve yeri yarattığım, Ay’a ve Güneş’e şekil verdiğim ve Güneş’in etrafına dokunulmaz olan yedi meleği yerleştirdiğim gün yarattım. O (Bekke), insanlarına süt ve su ile yardım eden iki tepesi varoldukça varolmaya devam edecektir.” Bir parça yazı da İbrahim makamında, Kâ’be’nin kapısı yanında İbrahim’in ayak izini taşıyan kayanın altında bulundu: “Mekke, Tanrı’nın kutsal evidir. Onun sürekliliği üç yönden gelir. Onun yakınındaki insanlar onu ilk kirletenler olmasın.”
Kureyşliler, binanın yüksekliğini arttırmak için daha çok taş topladılar. Ayrı ayrı kabileler sırayla çalıştılar. Nihayet bina Haceru’l-Esved’in konulacağı yüksekliğe geldi. Bu sırada aralarında şiddetli bir tartışma çıktı. Çünkü hiçbiri Haceru’l-Esved’i duvara yerleştirme şerefini, diğer kabileye bırakmak istemiyordu. Bu tartışma birkaç gün sürdü ve anlaşmazlık o denli büyüdü ki, taraflar savaşmaya hazırlandılar. O sırada yaşlı bir adam şöyle bir öneri getirdi: “Ey Kureyşliler, tartıştığınız konuda sizi uzlaştıracak bir hakem seçin. Mescid’e girecek olan ilk adam bu konuda hakem olsun.”[31] Kâ’be’nin çevresindeki alana Mescid, yani secde edilen yer adı verilir. Çünkü Allah’ın Evi’ne yönelerek O’na secde etme geleneği, İbrahim ve İsmail’den beri devam edegeliyordu. Yaşlı adamın tavsiyesine uymaya karar verdiler. Mescid’e ilk giren kişi, belli bir süredir Mekke’de bulunmayan ve henüz dönen Muhammed (s.a.v.) idi. Onun kapıdan görünmesiyle insanların yüzünde, mutluluk ve sevinç ifadeleri belirdi. Daha da yaklaştığında memnuniyetle dolu selâmlamalar ve mırıldanmalar topluluğu sardı. Bazıları: “O, el-Emîn’dir” dediler. Bazıları: “Muhammed (s.a.v.) geldi, onun kararına uyarız” dediler. Meseleyi ona anlattıklarında o, “Bana bir parça kumaş getirin” dedi. Getirdiklerinde bezi yere yaydı. Haceru’l-Esved’i ortasına koydu. “Her kabile bezin bir ucundan tutsun” dedi. “Sonra hep birlikte onu kaldırın”. Taşı yeteri kadar yerden yükselttiklerinde, onu aldı ve Kâ’be’nin köşesine kendi elleriyle yerleştirdi ve böylece inşaat devam etti.