Secondo la tradizione popolare, Kılıç Ali Paşa chiese al sultano Murad III un terreno su cui costruire una moschea. Il sultano rispose che avrebbe dovuto costruire una moschea in mare, poiché Kılıç Ali Paşa era un ammiraglio di grande valore. Questo spiega perché fu utilizzato del materiale di riempimento per creare un promontorio sulla costa e perché il complesso fu costruito in quella posizione. Un ampio cortile circonda la moschea e un tetto spiovente copre l'area di assemblea, con elaborate sculture sulle tre porte del giardino interno. Sopra le finestre sono dipinti versetti coranici su pannelli di ceramica.
Nel giardino si trova una fontana con otto colonne di marmo e una cupola di copertura. La moschea ha una pianta rettangolare ed è un ampliamento della Moschea di Santa Sofia. La parte superiore delle finestre è decorata con piastrelle e la cupola più grande poggia su quattro colonne di marmo a forma di zampa di elefante. Questa è sorretta a est e a ovest da due semicupole. In ognuno dei quattro angoli si trova una piccola cupola e piastrelle colorate con motivi floreali decorano l'interno della moschea. La cupola più grande ha ventiquattro finestre, portando il totale delle finestre dell'edificio a 147. Nel 1948 , la lanterna di una nave del XVI secolo, che pendeva dalla cupola principale, fu trasferita al Museo Navale di Istanbul. Sul lato destro si erge un minareto con balcone. La tomba di Kılıç Ali Paşa si trova nel giardino rivolto a est. Lungo il muro del giardino che si affaccia sulla strada si trova una fontana. L'hammam sul lato destro della moschea è ancora oggi in uso. La scuola si trova sul lato che si affaccia sull'hammam.
