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