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