بحسب الروايات الشعبية، طلب كليتش علي باشا من السلطان مراد الثالث أرضًا لبناء مسجد. فأجابه السلطان أن يبني المسجد في البحر نظرًا لعظمة كليتش علي باشا كقائد بحري. وهذا يفسر استخدام الردم لإنشاء نتوء أرضي على الساحل، وبناء المجمع في ذلك الموقع. يحيط بالمسجد فناء واسع، ويغطي قاعة الصلاة سقف مائل، وتزدان أبواب الحديقة الداخلية الثلاثة بنقوش بديعة. كما نُقشت آيات قرآنية على ألواح خزفية فوق النوافذ.
تضم الحديقة نافورة ذات ثمانية أعمدة رخامية وقبة. بُني المسجد على شكل مستطيل، وهو نسخة مكبرة من مسجد آيا صوفيا. تزين البلاطات قمم النوافذ، وترتكز القبة الكبرى على أربعة أعمدة رخامية على شكل أرجل فيل. يدعمها من الشرق والغرب قبتان نصفيتان. توجد قبة صغيرة في كل زاوية من الزوايا الأربع، وتزين البلاطات الملونة المزخرفة بنقوش زهرية داخل المسجد. تحتوي القبة الكبرى على 16 نافذة، ليصل إجمالي نوافذ المبنى إلى 147 نافذة. في عام 1948 ، نُقل فانوس السفينة الذي يعود للقرن السادس عشر - والذي كان معلقًا من القبة الرئيسية - إلى متحف إسطنبول البحري. على الجانب الأيمن، ترتفع مئذنة مع شرفة. يقع ضريح كليتش علي باشا في الحديقة المواجهة للشرق. بجوار جدار الحديقة المواجه للشارع، توجد نافورة. لا يزال الحمام الموجود على الجانب الأيمن من المسجد قيد الاستخدام حتى اليوم. تقع المدرسة على شاطئ الحمام.
