Bizans dövründə məscidin yerləşdiyi təpədə I Konstantinin dönəmində inşa edilən Havariyyun kilsəsi vardı. Bizans imparatorlarının bu təpədə basdırıldığına inanılır. Constantinusun o zamanlar şəhərin kənarında qalan bu təpədə basdırıldığı bilinməkdədir. İstanbulun fəthindən sonra bu bina Patrikxana kilsəsi olaraq istifadə edilmişdir. Fateh Sultan Mehmet buraya məscid və külliyyə insa etmək istəyincə patrikxana Pammakaristos manastırına köçürülmüşdür.

Tikintisinə 1462-ci ildə başlanıb, 1470-ci ildə tamamlanmışdır. Memarı Sinaüddin Yusuf bin Abdullahdır (Atik Sinan). Məscidə 1509-cu ildə İstanbul zəlzələsində böyük ziyan dəymiş və II Bəyazid dönəmində yenidən təmir edilmişdir. 1766-ci ildə baş verən bir zəlzələ ilə xaraba halına gəldiyi üçün Sultan III Mustafa 1767–1771-ci illər arasında məscidi memar Mehmed Tahir Ağaya təmir etdirmişdir. Buna görə də məscid orijinal görünüşünü itirmişdir. 29 yanvar 1932-ci ildə Türkcə azan bu məsciddə oxunmuşdur.

Məscidin ilk inşasından bu gün sadəcə şadırvan avlusunun üç divarı, şadırvan, tac qapı, mehrap, birinci şərəfiyəyə qədər minarələr və çevrə divarının bir qismi qalmışdır. Şadırvan avlusunda, qiblə divarına paralel olan Revak diğər üç yöndən daha yüksəkdir. Qübbələrin xarici hissəsi səggiz köşəli olub kəmərlərə oturdulub. Kəmərlər əsasən qırmızı daş və bəyaz mərmərlərlə işlənmiş, yalnız məhvərdəkilərə yaşıl daş istifadə edilmişdir. Alt və üst pəncərələrin ətrafı geniş silmələrlə əhatələnmişdir. Sövmələr mərmərdəndir və geniş, qüvvətli silmələrlə bağlanılmışdır.

Dəmir barmaqlıqlar, qalın dəmirdəndi və toppuzludur. Revak sütunlarının səggizi yaşıl eğriboz, ikisi pəmbə, ikisi qara qranitdən, son camaat yerindəkilərin bəziləri isə Misir qranitindəndir. Başlıqlar tamamən mərmərdəndir. Kaidələr də mərmərdir. Avlunun biri qiblədə, ikisi yanda üç qapısı vardır. Şadırvan səggiz köşəlidir. Mehrabın yaşmağı istalaktitlidir. Hücrə köşələri yaşıl dirəkli, qum saatlari ilə süslü və üstü zərif bir tacla tamamlanır. Yaşmağın üzərində bir sətrlik bir ayə vardır. İki dilimli olan minarə də cami ilə böyük bir ahəng təşkil edir. Çinili lövhələr son camaat divarının sağ ve solundakı pəncərə hissəsindədir.

Fateh məscidinin ilk tikilişində, məscidin ətrafını genişləndirmək üçün divarlar və iki ayaq üstündə bir qübbə oturdulmuş və bunun da önünə bir yarım qübbə əlavə edilmişdir. Beləlliklə 26 mt çapındaki qübbə bir yüz il boyunca ən böyük qübbə qədimliyi qorumuşdur. Məscid ikinci dəfə tikilişində payandalı məscid planı uyğunlaşdırlaraq kiçik qübbəli sivri bir bina meydana gətirilmişdir. İndiki durumda mərkəzi qübbə dörd fil yağına oturmaqla dörd yarım qübbə ilə əhatə edilmişdir.

Minarələrin daş külahları 19-cu əsrin sonunda inşa edilmişdir. Memar Mehmed Tahir Ağa məscidi təmir etdiyi zaman köhnə məsciddən qalan klassik parçalarla yenidən tikdiyi barok parçaları yaxşı bir şəkildə birləşdirdi. Məscidin gips pəncərələri son dövrlərdə xarab olduğundan adi çərçivələrlə dəyişdirildi. Həyət qapısının yanındakı yanğın hovuzu Sultan II Mahmud tərəfindən 1825-ci ildə inşa etdirildi. Məscidin geniş bir xarici həyəti vardı.

Başda Fateh Sultan Mehmetin türbəsi olmaqla, Osmanlı tarixinin bir çox əhəmiyyətli adamlarının məzarı buradadır. Fatehin həyat yoldaşı və II Bəyazidin anası I Gülbahar Xatunun, "Türkiyənin qəhrəmanı" Qazi Osman Paşanın və məsnəvi Abidin Paşanın türbələri məscid məzarlığındadır. Sədrəzəmlər, şeyxülislamlar, müşiri və bir çox elm adamının məzarlarının burada olması, Osmanlı protokolunun sanki toplantıdaymış kimi bir arada görülməsinə imkan verir. Məzarları burada olan bəzi dövlət adamları və elm mənsublarından bir neçəsi bunlardır:

• Sədrəzəm Mustafa Naili Paşa
• Sədrəzəm Abdurrahman Nurəddin Paşa
• Sədrəzəm Qazi Ahmed Muhtar Paşa
• Şeyxülislam Amasyevi Seyyid Xəlil Əfendi
• Şeyxülislam Mehmed Refik Əfendi
• Ahmet Cevdet Paşa
• Emrullah Efendi]]. Maarif Nazırı.
• Yesari Mehmed Esad Efendi]]. Hattat.
• Yesarizade Mustafa İzzet Efendi]]. Hattat.
• Sami Efendi -xəttat.
• Amiş Efendi Mutasavvıf ve Fatih türbedarı.
• Maraşlı Ahmed Tahir Efendi — Amiş Efendinin tələbəsi.
• Kazasker Mardini — Yusuf Sıdkı Efendi.
• Manastırlı İsmail Hakkı Efendi — Selatin məscidləri vaizi.
• Şehbenderzade Ahmed Hilmi Bəy — Darülfünun Felsefe müdiri və ədib.
• Bolahenk Mehmed Nuri Bəy — Musıqişünas, xoca ve bəstəkar.
• Ahmed Midhat Efendi
• Köse Raif Paşa
• Akif Paşa
• Sultanzadə Mahmud Cəlaləddin Bəyəfəndi
• Xariciyyə Naziri Vəliyüddin Paşa
• Xariciyyə Naziri Mehmed Raşid Paşa
• Hacə İshak Əfendi
• Ferik Yanyalı Mustafa Paşa
• İbrahim Subaşı (Tokatlı)
• General Pertev Demirxan