فانطلق الكلبيون، فأعلموا أباه فَقَالَ: ابني ورب الكعبة، ووصفوا له موضعه، وعند من هو. فخرج حارثة وكعب ابنا شراحيل لفدائه، وقدما مكة فسألا عن النبي ﷺ، فقيل: هو في المسجد، فدخلا عليه، فقالا:
يا بن عبد المطلب، يا بن هاشم، يا بن سيد قومه، أنتم أهل حرم الله وجيرانه، تفكون العاني، وتطعمون الأسير، جئناك في ابننا عندك، فامنن علينا، وأحسن إلينا في فدائه. قَالَ: ومن هو؟ قالوا: زيد بن حارثة. فقال رسول الله ﷺ: فهلا غير ذَلِكَ! قالوا: وما هو؟ قَالَ: أدعوه فأخيره، فإن اختاركم فهو لكم، وإن اختارني فو الله ما أنا بالذي أختار على من اختارني أحدا.
قالا: قد زدتنا على النصف، وأحسنت. فدعاه فَقَالَ: هل تعرف هؤلاء؟ قَالَ: نعم.
قَالَ: من هذا؟ قَالَ: هذا أبي. وهذا عمي. قَالَ: فأنا من قد علمت ورأيت صحبتي لك، فاخترني أو اخترهما. قَالَ زيد: ما أنا بالذي أختار عليك أحدا، أنت مني مكان الأب والعم. فقالا: ويحك يا زيد! أتختار العبودية على الحرية وعلى أبيك وعمك، وعلى أهل بيتك! قَالَ: نعم، قد رأيت من هذا الرجل شيئا.
ما أنا بالذي أختار عليه أحدا أبدا. فلما رأى رسول الله ﷺ ذلك أخرجه إلى الحجر، فقال: يأمن حضر. اشهدوا أن زيدا ابني يرثني وأرثه. فلما رأى ذَلِكَ أبوه وعمه طابت نفوسهما فانصرفا. ودعي زيد بن محمد، حتى جاء الإسلام فنزلت: ادْعُوهُمْ لِآبائِهِمْ ٣٣: ٥. فدعي يومئذ زيد بن حارثة، ودعى الأدعياء إلى آبائهم، فدعي المقداد بن عمرو، وكان يقَالُ له قبل ذَلِكَ المقداد بن الأسود، لأن الأسود بن عبد يغوث كان قد تبناه.