Në vendndodhjen e rrënojave të kësaj xhamie, e vendosur brenda kështjellës së vjetër të Krujës dhe pak metra pas portës kryesore, mund të ketë qenë xhamia e ndërtuar nga Sulltan Mehmeti. Emri i ndërtesës është ruajtur nga vendasit. Meqë sulltani vdiq në vitin 1481, periudha në të cilën mund të jetë ndërtuar kjo xhami është e kufizuar. Xhamia, ashtu sikurse edhe hamami aty pranë, ka shërbyer padyshim për nevojat e garnizonit. Kjo xhami e vjetër mund të jetë dëmtuar në vitin 1831, kur ushtria osmane shpërtheu muret e kështjellës gjatë kryengritjes së antitanzimatit. Xhamia, apo së paku minarja e saj, është rindërtuar në vitin 1253 H (7.4. 1837- 26.3.1838) dhe ka shumë mundësi të jetë bërë me shpenzimet e Sulltan Mahmudit II.
Rrënojat që shohim sot (1978) janë të kufizuara tek muret e themelit të një salle drejtkëndore faljeje dhe trungut të minares. Salla e faljes ka përmasa 11.50m e gjatë dhe 10.90m e gjerë nga jashtë. Muret kanë qenë 0.78m të trashë, trashësi kjo e pamjaftueshme për të mbajtur ndonjë lloj kubeje prej guri. Për më tepër, muri është i ndërtuar nga gurë rrënojash apo gurë të punuar pak, një tjetër tregues që ndërtesa ka qenë një sallë e thjeshtë, e lyer me gëlqere dhe e mbuluar me dru. E gjithë përkujdesja ka qenë e fokusuar tek minarja. Ajo përbëhet nga një bazë e gjatë katrore, e ndërtuar me blloqe të prerë mirë prej guri të bardhë dhe zona kalimtare ka qenë e ndërtuar me tulla, poshtë trupit të minares. Fillimet e trupit me kanalyra të minares janë pak të dukshme.
Xhamia dhe minarja janë strukturalisht të lidhura së bashku, pa ndonjë fugë midis tyre. Kjo më bën të besoj se e gjithë ndërtesa është rikonstruktuar nga Mahmudi II. Data e ndërtimit është dhënë në një zbukurim në formë dorëshkrimi në anën jugperëndimore të minares, viti 1253. Afër mbishkrimit ndodhet një gjysmëhënë me një yll me tetë cepa, i vetmi zbukurim në këtë pjesë të ndërtesës. Nga një fotografi e vjetër, e botuar nga Frashëri dhe Dashi, mësojmë se xhamia ekzistonte edhe pas Luftës II Botërore. Nga fotografia dallohet se ajo mund të ketë qenë rindërtuar plotësisht në vitin 1253 (A.D. 1837/38). Stili i ndërtesës e bën këtë fakt shumë të qartë.