بناء المسجد شرع رسول الله ﷺ منذ وصل إلى المدينة في بناء مسجده في المكان الذي بركت فيه ناقته، وكان هذا المكان مربدًا١ للتمر مملوكًا لغلامين يتيمين في المدينة٢، فدعا رسول الله ﷺ بالغلامين، وطلب إليهما المريد ليتخذه مسجدًا وتحدث معهما في شرائه ... فقالا: بل نهبه لك يا رسول الله. فأبى ﵇ أن يقبله منها هبة، ولكنه ابتاعه منهما٣. وكان فيه قبور للمشركين وبعض حفر ونخل، فأمر رسول الله ﷺ بالقبور فنبشت، وبالحفر فسويت، وبالنخل فقطع. ثم أمر بالبناء، وكان بناؤه باللبن٤، ولكن عضادتي الباب كانتا من الحجارة، وكان سقفه من الجريد، وأعمدته من جذوع النخل، ولا يزيد ارتفاعه عن القامة إلا القليل. وقد اشترك رسول الله ﷺ وأصحابه في حمل اللبنات والأحجار على كواهلهم، وكانوا يروحون عن أنفسهم عناء الحمل والنقل والبناء فيرددون هذا الغناء:

١ المريد: موضع تجفيف التمر. ٢ هما: سهل وسهيل ابنا عمرو. ٣ لفظ البخاري: "فقالا: بل نعطيه رسول الله ﷺ، ويقال: بل اشتراه منهما" ولم يجزم بأحد الأمرين، لكن وقع الجزم في رواية أخرى وأنه اشترى. ٤ الطوب.