Oryginalny meczet został zbudowany przez Mahometa i jego towarzyszy obok domu, w którym zamieszkał po swoim przybyciu do Medyny w 622 r. Postawiony został na planie prostokąta o wymiarach 30 m na 35 m i wysokości 2 m. Ściany wykonane były z pni palmowych i błota, a dach pokrywały liście. Do środka prowadziły trzy wejścia: od strony południowej Bab ar-Rahma (Drzwi Miłosierdzia), od zachodu Bab Dżibril (Drzwi Gabriela), a od wschodu Bab an-Nisa (Drzwi Kobiet).
Wewnątrz Mahomet utworzył zacieniony obszar w południowej części budynku zwany suffah, a przestrzeń modlitewną skierował na północ w stronę Jerozolimy. Później, kiedy kibla, czyli kierunek modlitwy, został zmieniony w stronę Al-Kaby w Mekce, meczet także ukierunkowano na południe.
Siedem lat później w 629 r. meczet rozbudowano i zwiększono jego powierzchnię niemal dwukrotnie, żeby pomieścić wzrastającą liczbę wiernych. Otoczono go również 35 kolumnami.
Meczet pozostał w niezmienionym stanie do czasu rządów kalifa Umara, który powiększył jego obszar do 3575 m² i postawił drewniane kolumny.
Z kolei Usman ibn Affan dobudował kamienne arkady i otynkował budynek, jak również zmienił kolumny na kamienne.