Η κατασκευή του τζαμιού ξεκίνησε το 1597. Η κατασκευή του διατάχθηκε από την Σαφιγιέ Σουλτάν,η οποία ήταν η σύζυγος του Σουλτάνου Μουράτ Γ' και αργότερα Βαλιντέ Σουλτάν (Βασιλομήτωρ) του Σουλτάνου Μεχμέτ Γ'. Διέταξε την κατασκευή του τζαμιού υπό την ιδιότητά της ως βαλιδέ σουλτάνα, δύο χρόνια μετά την άνοδο του Μεχμέτ Γ' στον Οθωμανικό θρόνο το 1595, εξ ου και η αρχική επίσημη ονομασία "Βαλιντέ Σουλτάν Τζαμί".

Ο αρχικός αρχιτέκτονας ήταν ο Νταβούτ Αγά, μαθητευόμενος του μεγάλου Μιμάρ Σινάν. Ωστόσο, ο Νταβούτ Αγά πέθανε το 1599 και αντικαταστάθηκε από τον Νταλγκίτς Αχμέτ Τσαβούς. Η κατασκευή διήρκεσε περισσότερο από μισό αιώνα και ολοκληρώθηκε από μια άλλη βαλιδέ, την Τουρχάν Χατιτζέ Σουλτάν, μητέρα του Σουλτάνου Μεχμέτ Δ'.

Το έργο παρεμποδίστηκε από την πολιτική αποσύνδεση,και τη θέση του και τις νομισματικές επιπτώσεις που δημιούργησαν διαφωνία στο δικαστήριο. Η γειτονιά Εμίνονου ήταν κύριο εμπορικό κέντρο της πόλης,και το σπίτι σε κατά κύριο λόγο εβραϊκό πληθυσμό. Με την τοποθέτηση του τζαμιού εκεί, η Σαφιγιέ Σουλτάν ήλπιζε να επεκτείνει τη σφαίρα της ισλαμικής επιρροής μέσα στην πόλη,αξιοποιώντας την αυξανόμενη δυσαρέσκεια των ντόπιων και ξένων εμπόρων που προκαλούνταν από την αυξανόμενη δύναμη και την επιρροή των Εβραίων με τα ομολογά τους,τα οποία έδωσαν στο Σουλτάνο μια εύκολη δικαιολογία για την δήμευση της περιουσίας τους. Ωστόσο, η μεγάλη νομισματική δαπάνη επέστησε έντονη κριτική. Ειδικότερα, οι γενίτσαροι αγανάκτησαν με την αυξανόμενη πολιτική δύναμη της Σαφιγιέ Σουλτάν, και πίστευαν ότι το τζαμί ήταν μια περιττή δαπάνη. Η Σαφιγιέ Σουλτάν αναγκάστηκε να εγκαταλείψει το σχέδιο μετά το θάνατο του γιου της, Μεχμέτ Γ' το 1603. Ο νέος σουλτάνος​​, Αχμέτ Α', δεν είχε κανένα ενδιαφέρον για να συνεχιστεί το έργο μετά η Σαφιγιέ Σουλτάν είχε υποβιβαστεί στο χαρέμι ​​και η κατασκευή εγκαταλείφθηκε.

Μετά το 1603, η εν μέρει κατασκευασμένη δομή μειώθηκε σταδιακά σε ερείπια και υπέστη σοβαρές ζημιές κατά τη διάρκεια της μεγάλης πυρκαγιάς της Κωνσταντινούπολης (1660), η οποία άρχισε στις 24 του Ιουλίου 1660 και διήρκεσε λίγο περισσότερο από δύο ημέρες(περίπου 49 ώρες, σύμφωνα με τα χρονικά του Αμπντί Πασά) και κατέστρεψε πολλές γειτονιές της πόλης. Αργότερα εκείνο το έτος,ο αυτοκρατορικός αρχιτέκτονας Μουσταφά Αγά πρότεινε στην Τουρχάν Χατιτζέ Σουλτάν, μητέρα του Μεχμέτ Δ', να ολοκληρώσει το τζαμί ως έργο ευσέβειας. Η Τουρχάν Χατιτζέ Σουλτάν διέταξε επίσης την κατασκευή του κοντινού Παζαριού Μπαχαρικών, το οποίο αποτελεί μέρος του κουλιγιέ του Νέου Τζαμιού. Έτσι, κατά τους τελευταίους μήνες του 1660, η κατασκευή του τζαμιού επαναλαμβάνεται, ενώ η κατασκευή του διπλανού παζαριού ξεκίνησε.

Το τζαμί ολοκληρώθηκε τελικά το 1663 και εγκαινιάστηκε το 1665.