La construcció de la mesquita començà el 1597 amb el mandat de la soldana Safiye Valide Sultan, muller del soldà Murat III. Fou iniciada per l'arquitecte Davut Agha, continuada per Dalgç Ahmed Agha i finalment acabada per Mustafa Agha durant el regnat del soldà Mehmet IV el 1663. Els blocs de pedra utilitzats en la construcció de la mesquita foren proveïts des de l'illa de Rodes.

La mesquita prové de l'època en què unes avesades dones de l'harem van aconseguir el poder suficient per a dictar la política dels soldans otomans. La construcció va durar 66 anys a causa de les morts inoportunes de Mehmet III, fill de Safiye i la consegüent pèrdua del seu rang, i una epidèmia general a Istanbul durant els primers anys de construcció.