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