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