Frazsız arxeoloq Kamil Enlart məscidin yerləşdiyi yerdə 14 və 15-ci əsrlərdə, Kipr krallığı və Venesiya Respublikası dövründə karmelit kilsəsinin mövcud olduğunu söyləmişdir. Kilsənin bir günbəzi olduğu və Qüds kralı, Normandiya hersoqu və digər zadəganların dəfn olunduğu bir qəbiristanlıqla əhatə olunduğu bildirilir. 1571-ci ildə Osmanlının Kipri fəth etməsindən sonra Sarayönü meydanında ordu düşərgəsi quruldu və Karmelit kilsəsi əsgərlərin ibadətini asanlaşdırmaq üçün məscidə çevrildi. Bu dövrdə binanın xarici görünüşü Qotik üslubu əks etdirdiyi halda, daxili görünüşü klassik Osmanlı memarlığını sərgiləyirdi. Məscid bu dövrdə "Orduönü məscidi" adlandırılmışdır.

Daha sonralar Osmanlı hakimiyyəti dövründə ərazidə yeni bir məscid inşa edildi. Bu məscidin tikilmə tarixi üçün təsminlər müxtəlifdir: bəzi mənbələr məscidin inşaatını 1690-1691-ci illərdə Qılınc Əli paşaya aid edərkən, bəziləri də 1820-1824-cü illərdə, Əli Paşaya aid edir.

Məscidin içərisində Osmanlı memarlığının ənənəvi xüsusiyyətlərindən biri olan, iki iti tağ və bəzəksiz minarə ilə dəstəklənmiş dam var idi. 1873-cü ildə məscidi ziyarət etmiş A.L. Salvator məscidin həyətində yunan yazıları olan sarkofaqın olduğunu və namazdan əvvəl dəstəmaz üçün istifadə edildiyini yazmışdır. Sarkofaq 1980-ci ildə Heydərpaşa məscidinə həyətinə köçürüləcəkdi.

Məscid 1900-cü ilin yanvarında baş verən zəlzələ nəticəsində zərər gördü. Həmin il ingilis memar Fenton Atkinso hazırkı məscidin layihəsini hazırladı. İddialara görə Atkinson Əndəlüs xatirələrindən ilham almışdı. İndiki məscidin inşası 26 noyabr 1901-də başlamış və 1903-cü ildə başa çatmışdır.

1963-1964-cü illərdə Qanlı Milad adlanan icmalararası qarşıdurmadan sonra Kipr türklərinin rəsmi evlilik mərasimləri keçirəcək binası yox idi. Beləliklə məscid evlilik ofisinə çevrildi. İddialara görə döşəmədəki xalçalar çıxarılmış və məscidə skamyalar qoyulmuşdu. Tikili 2004-cü ildə, Türkiyənin milli qəzeti Zaman da daxil olmaqla mühafizəkar və mötədil İslamçı dairələrin təzyiqindən sonra yenidən məscidə çevrildi.

Məscid Mavr memarlıq üslubunda dizayn edilmişdir və eyni zamanda bəzi Hindistan təsirlərini də özündə cəmləşdirir. Bununla birlikdə layihəsi düzbucaqlıdır və buna görə ənənəvi Kipr stilinə uyğundur. Xarici təsirləri aydın göstərən ön fasadı iti nal şəkilli tağlarla bölünmüş beş hissədən ibarətdir. Əvvəlki Osmanlı məscidindən olan minarə, daşdan və məscidin əsas hissəsindən ayrılmış dayaqlardan düzəldilmişdir.