नबी सल्लल्लाहु अलैहि व सल्लम की उम्र जब पैंतीस वर्ष हुई, तो क़ुरैश ने काबा का नए सिरे से निर्माण करने का फ़ैसला किया, क्योंकि हज़रत इस्माईल अलैहिस्सलाम के दौर से बनी नौ हाथ ऊंची व बिना छत वाली इमारत जर्जर हो चली थी, चोरों ने भीतर रखा ख़ज़ाना चुरा लिया था और उसी साल आई एक भारी बाढ़ ने दीवारों को और कमज़ोर कर दिया था, जिससे इमारत के ढहने का ख़तरा पैदा हो गया था। क़ुरैश ने सर्वसम्मति से तय किया कि निर्माण में सिर्फ़ हलाल कमाई का धन इस्तेमाल होगा, वेश्यावृत्ति, सूद या नाहक़ छीने गए माल का पैसा शामिल नहीं होगा। पुरानी इमारत को ढहाने की हिम्मत पहले किसी में न हुई, आख़िर वलीद बिन मुग़ीरा ने अल्लाह का नाम लेकर शुरुआत की और जब किसी अनहोनी का सामना न हुआ, तो बाक़ी लोगों ने भी ढहाना शुरू कर दिया, यहां तक कि हज़रत इब्राहीम अलैहिस्सलाम की रखी बुनियाद तक पहुंच गए। निर्माण के लिए हर क़बीले को अलग हिस्सा दिया गया और एक रूमी कारीगर बाक़ूम की निगरानी में काम शुरू हुआ। जब दीवार हजरे अस्वद (काले पत्थर) की जगह तक पहुंची, तो यह झगड़ा खड़ा हो गया कि इस सम्मानित पत्थर को उसकी जगह रखने का गौरव किस क़बीले को मिले, यह विवाद चार-पांच दिन तक इतना बढ़ गया कि ख़ून-ख़राबे की नौबत आने लगी। आख़िरकार अबू उमैया मख़्ज़ूमी के सुझाव पर तय हुआ कि जो भी व्यक्ति सबसे पहले मस्जिदे हराम के दरवाज़े से प्रवेश करे, उसे इस झगड़े का मध्यस्थ (फ़ैसला करने वाला) मान लिया जाए। इत्तेफ़ाक़ से सबसे पहले नबी सल्लल्लाहु अलैहि व सल्लम ही अंदर दाख़िल हुए, जिन्हें देखकर सब ख़ुश होकर बोल उठे कि यह अमीन (भरोसेमंद) हैं, हम इनके फ़ैसले पर राज़ी हैं। नबी सल्ल० ने एक चादर मंगवाई, बीच में हजरे अस्वद रखा और सभी क़बीलों के सरदारों से कहा कि वे सब मिलकर चादर के किनारे पकड़कर उसे ऊपर उठाएं; जब चादर हजरे अस्वद की तयशुदा जगह तक पहुंच गई, तो आपने अपने मुबारक हाथों से पत्थर को उसकी जगह रख दिया, इस बुद्धिमानीपूर्ण फ़ैसले से पूरी क़ौम संतुष्ट हो गई और ख़ूनी टकराव टल गया। बाद में हलाल धन की कमी की वजह से क़ुरैश ने उत्तर दिशा से काबा की लंबाई क़रीब छह हाथ कम कर दी, जो हिज्र या हतीम कहलाता है, और दरवाज़ा भी ज़मीन से ऊंचा बनाया ताकि सिर्फ़ मनचाहे लोगों को ही भीतर आने दिया जा सके।