Bugün Eminönü denilen yerde bulunan Yeni Cami'nin temeli 1597 yılında atıldı. Sultan III. Mehmed'in tahta geçişiyle Valide sultan namı ile bütün nüfuz ve hükmü eline alan ve hatta siyasî işlere bile karışmaya başlayan Safiye Sultan, hayrat ve hasenatla şerefini yükseltmek arzusunu duyunca bir cami yaptırmaya karar verdi. Camiin inşası için seçilen Bahçekapı çevresi o tarihlerde gümrüğe ve limana yakınlığı dolayısıyla bir ticaret yeri, oldukça sıkışık, aynı zamanda bakımsız bir Yahudi ve Hıristiyan mahallesiydi. Camiin inşaat sınırları içinde bir kilise ve bir sinagog vardı. İstimlâk edilecek evlere iki kat bedel verilmesi; sinagog ve kilise yerine de iki harap mabedin tamiri kararlaştırıldı.
Mimarlığa Ser Mimaran-ı Alem Davud Ağa getirildi. Davud Ağa, Mimar Sinan'ın yetiştirmelerindendir. Sinan'ın sağlığında bizzat yaptırdığı eserlere adını yazdırmak şerefine nail olmuştu. Eskiden surlarla çevrili olan Eminönü'nün dışa açılan bazı kapıları vardı: Bahçe kapısı, Çıfıt kapısı ve Balık pazarı kapıları. Bugün deniz ile cami arasında bulunan geniş alan ise tamamen denizle kaplıydı. İşte Yeni Cami'nin inşaat alanının böyle deniz seviyesinde ve dolma bir arazi olması nedeniyle temel çukurlarında su çıkmaya başlayınca gece gündüz demeden tulumbalarla bu su boşaltılmaya başlandı. Daha sonra Davud Ağa, Mimar Sinan'ın Büyükçekmece köprüsünde yaptığı gibi, büyük kazıklar çaktırıp, bunların başlarını kurşun kuşaklarla birleştirmiş ve binanın temel taşlarını bu tabanlara oturtmuştur. Bugüne kadar Haliç kıyılarında çökme ve kaymalar olmasına karşılık bu büyük eserin, birçok zelzelelerle ve dış etkiler dahil olduğu halde hiçbir arızaya uğramamış bulunması temellerinin salâbet ve mükemmelliğine delildir. 1598 yılında İstanbul'da meydana gelen bir veba salgınında Mimar Davud Ağa'nın Ölmesi üzerine, camiin mimarlığına Dalgıç Mehmed Çavuş getirildi. 1603 yılında III. Mehmed ve arkasından da Safiye Sultan'ın ölümü üzerine inşaat yarım kaldı. Yapı ilk pencere taklarına kadar yükselmişti. Aradan yıllar geçti ve çevreyi yine yahudi evleri kapladı, her yer mezbelelik halini aldı. 1660 yılında meydana gelen ve İstanbul halkını acı ve sefalet içinde bırakan yangından Bahçe kapısı çevresi de etkilenmiş, buralar harap hale gelirken Yeni cami de hasara uğramıştı. Bu sırada İstanbul halkına yardım için yangın yerlerini gezen Sultan IV. Mehmed'in validesi Turhan Sultan, bu camiin yarım bırakılmış duvarlarına rastladı.
O sıralarda bir cami yaptırmayı düşünen Valide Sultan, bu abideyi kurtarmak düşüncesiyle 1660 yılında, yani inşaatın durdurulmasından 59 yıl sonra, duvarlarından bir sıra taş sökülerek yapıyı yeniden başlattı. Mimarlığına Ser Mimar-ı Hassa Mustafa Ağa tayin edilmişti. Nihayet camiin yapımı 1663 yılında tamamlandı. 5 Rebiül ahir günü mevlit okunup Cuma namazı kılınarak açılış töreni yapıldı. Bu törende Valide sultan, IV. Mehmet ve Köprülü "Fazıl Ahmed Paşa ile bütün vüzera ve ulema hazır bulundu. Turhan Sultan, oğlundan başlayarak bütün davetlilere kıymetli hediyeler dağıttı, Bütün devlet erkânı da en süslü, pahalı ve değerli halı ve avizelerle camii donattılar.
