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