A construção da mesquita iniciou-se em 1597, por ordem da valide sultana Safia Sultana, a consorte principal do sultão Murade III e mãe de Maomé III, o Justo. O primeiro arquiteto foi Davut Aga, um aprendiz do grande mestre Mimar Sinan. Davut morreu em 1599, sendo substituído por Dalgic Ahmed Cavus.

O projeto foi estorvado por diversas questões políticas, nomeadamente pela sua localização ter provocado polémica na corte. O bairro de Eminönü era o principal centro comercial da cidade e era habitado sobretudo por judeus. Com a construção da mesquita neste local, Safia esperava ampliar a influência muçulmana sobre a cidade, capitalizando o descontentamento crescente de comerciantes locais e estrangeiros em relação ao poder e influência cada vez maiores dos comerciantes judeus, que deu à valide sultana uma boa justificação para confiscar propriedades de judeus. No entanto, os elevados custos do projeto levantaram fortes críticas, nomeadamente dos janízaros, os militares de elite otomanos, a quem não agradava o poder crescente da valide sultana e que advogavam que a mesquita era uma despesa desnecessária. Safia Sultana foi forçada a abandonar o projeto após a morte de Maomé III. O sultão que lhe sucedeu, Amade I não estava interessado no projeto da mesquita, cuja construção foi abandonada quando Safia foi relegada para o harém.

A estrutura parcialmente construída caiu em ruínas e foi muito danificada por um fogo em 1660. No mesmo ano, o arquiteto imperial Mustafá Aga sugeriu à valide sultana Turhan Hadice, mãe do sultão Ibraim I, que completasse a obra como prova de devoção. A mesquita seria concluída em 1663 e inaugurada em 1665.