मदीना में दाख़िल होते ही नबी सल्लल्लाहु अलैहि व सल्लम ने अपनी ऊंटनी की लगाम ढीली छोड़ दी और फ़रमाया कि यह अपनी मर्ज़ी पर छोड़ी गई है, यही जहां बैठेगी मेरा ठिकाना होगा। ऊंटनी घूमती हुई आख़िर उस ज़मीन पर बैठी जो दो यतीम भाइयों सहल व सुहैल बिन अम्र की मिल्कियत थी और जिसमें मुशरिकों की कुछ क़ब्रें, कुछ वीरान ज़मीन और खजूर व अन्य पेड़ थे। नबी सल्ल० ने इन यतीम बच्चों को बुलाकर ज़मीन की क़ीमत पूछी, वे इसे मुफ़्त देना चाहते थे, लेकिन आपने ज़िद करके उन्हें क़ीमत अदा की। इसके बाद मुशरिकों की क़ब्रें उखड़वाई गईं, वीरान ज़मीन बराबर कराई गई और पेड़ काटकर क़िबले (उस वक़्त बैतुल मक़दिस) की तरफ़ इस्तेमाल किए गए। दरवाज़े के दोनों तरफ़ पत्थर के खम्भे बनाए गए, दीवारें कच्ची ईंट व गारे से बनीं, छत खजूर की शाख़ों व पत्तों से और खम्भे खजूर के तनों से बनाए गए, ज़मीन पर रेत व कंकरियां बिछाई गईं और तीन दरवाज़े रखे गए। मस्जिद की लम्बाई-चौड़ाई क़रीब सौ हाथ थी। मस्जिद के बाज़ू में नबी सल्ल० की पत्नियों के लिए कच्ची ईंट व खजूर की शाख़ों से बने कुछ हुजरे (कोठरियां) भी बनाए गए, जिनके पूरा होने पर आप हज़रत अबू अय्यूब अंसारी रज़ि० के घर से यहां आ गए। यह मस्जिद केवल नमाज़ की जगह नहीं, बल्कि एक तरह की यूनिवर्सिटी थी, जहां मुसलमान इस्लामी शिक्षाएं व हिदायतें सीखते, एक ऐसी महफ़िल थी जहां वर्षों की अज्ञानतापूर्ण दुश्मनी वाले क़बीले अब मेल-मुहब्बत से मिल-जुलकर बैठते, साथ ही यह छोटी सी इस्लामी रियासत का प्रशासनिक केंद्र और मजलिसे शूरा (परामर्श सभा) के लिए एक तरह की पार्लियामेंट भी थी। इसके अलावा यह उन ग़रीब मुहाजिरों का ठिकाना भी बनी, जिनका मदीना में न कोई घर था, न माल, न बीवी-बच्चे। हिजरत के शुरुआती दिनों में ही अज़ान की भी शुरुआत हुई, जिसकी प्रेरणा एक बुज़ुर्ग सहाबी हज़रत अब्दुल्लाह बिन ज़ैद बिन अब्द रब्बिही रज़ि० को सपने में मिली और नबी सल्ल० ने उसे मंज़ूरी दे दी, यह रोज़ पांच बार फ़िज़ा में गूंजने वाला एक ऐसा एलान बना, जिसमें तौहीद और नबी सल्ल० की रिसालत की गवाही दी जाती।