Sous les Ottomans, il était de coutume qu’un brave guerrier ou un chef d’armée fasse construire sa propre mosquée après une ou plusieurs victoires. On se rendait devant le sultan qui, comme récompense, désignait l’endroit où allait être édifier le nouveau sanctuaire à la gloire de Dieu. L’amiral d'origine italienne, Kiliç Ali Pacha après s’être distingué dans plusieurs batailles navales, se présenta au palais. Pour des raisons que l’on ignore, le sultan le détestait, mais selon la tradition, ne pouvait lui refuser sa requête. Il lui dit donc : « Puisque tu es le maître de la mer, va donc construire ta mosquée sur la mer ». Il lui désigna le terrain marécageux de Tophane qui dut être complètement remblayé avant d’entreprendre les travaux.
La mosquée est entourée d'un hammam, d'une école et d'une fontaine monumentale.