Toen de profeet, Allah's zegen en vrede zij met hem, vijfendertig jaar oud was, vond een overstroming plaats die de muren van de Ka'bah beschadigde. Aangezien de muren al eerder waren beschadigd door een brand, vonden de mensen van Quraish het noodzakelijk om ze te herbouwen. Zij besloten daarop om de bouw alleen te financieren met het eerlijk verdiende geld, dus niet het geld van de bruidschat van een prostituee, het geld afkomstig van renteheffingen of dat ten onrechte afgenomen was van een ander.

Zij vreesden Allah's bestraffing als zij het zouden slopen, maar toen vertelde Alwalied, de zoon van Almoughirah hen: 'Allah bestraft niet degenen die iets herstellen' en begon zelf met het slopen. Zij volgden hem hierin totdat ze de fundamenten van Ibrahiem bereikten. Zij startten de bouw van de Ka'bah en verdeelden de bouwactiviteiten onder de verschillende stammen. De vooraanstaanden droegen de stenen op hun schouders. De profeet, Allah's zegen en vrede zij met hem, en zijn oom Al'abbas deden hetzelfde. Een Romeinse bouwer, wiens naam Baaqum was, was verantwoordelijk voor de bouw. Later bleek dat de -eerlijk verdiende- financiële middelen niet voldoende waren om de bouw vanaf de fundamenten van Ibrahiem te beëindigen, zij lieten daarom ongeveer zes meter open en bouwden een muurtje aan de rand van de oorspronkelijke grenzen als aanwijzing dat het bij de Ka'bah behoorde. Dit deel wordt de "Alhajar wal-hutaim" genoemd.

Bij het bereiken van de plek van de zwarte steen "alhajar alaswad" tijdens de bouwwerkzaamheden wilde elk stamhoofd zichzelf de eer verschaffen om de steen op zijn plek terug te leggen.

Dit leidde tot flinke ruzies onderling, die vier tot vijf dagen duurden. De situatie dreigde in een bloedige strijd te veranderen, maar de wijze Abu Umayya, de zoon van Almughierah Almakhzoumi, heeft dit kunnen voorkomen. Hij was de oudste man van Quraish en stelde voor om de arbitrage over te laten aan de eerste man die zou binnenkomen in de moskee en allen stemden daarmee in.

De voorbestemming van Allah was dat die eerste man die zou binnen- komen na dit besluit, de profeet zou zijn, Allah's zegen en vrede zij met hem. Toen de mensen hem zagen zeiden ze: 'Deze man is de betrouwbare en wij accepteren hem, dat is Mohammed'. Toen hij bij hen aankwam vertelden zij het verhaal, hij pakte een mantel, legde de zwarte steen erin en vroeg een ieder die mantel vast te houden en hem vervolgens te dragen naar de plek van de steen. Toen zij die hadden bereikt, pakte Mohammed, Allah's zegen en vrede zij met hem, de steen en legde die op zijn plaats. Het was de juiste oplossing waar iedereen over tevreden was.

De zwarte steen lag anderhalf meter hoog en de deur van de Ka'bah lag twee meter boven de grond zodat alleen degenen waar zij toestemming aangaven naar binnen konden.
Zij hebben de hoogte van de muren verdubbeld en deze werden ongeveer acht meter (18 thira'e). Zij legden zes pilaren neer binnen de Ka'bah in twee rijen en maakten daarboven het plafond, ter hoogte van vijftien Thira'e, dat ongeveer zeven meter is. De Ka'bah was voor deze renovatie namelijk zonder plafond of pilaren.