Uzun yıllar bakım ve yenileme yapılarak ibadete açılarak ibadete açık tutulduğundan çok iyi bir durumda günümüze kadar gelmiştir.
1298 - 1312 yılları arasında St. Nicolas Katedrali adıyla yapılmıştır. Mimari ve tasarımcısı Piskopos Baldwin Lambert gösterilmektedir. Yapımına işaret eden I/IX/1311 tarihi, güney duvarında kayıtlıdır. Yapıldığı dönemde Lüzinyan kralları Kıbrıs krallık tacını ilkin Lefkoşa’daki St. Sophia Katedrali’nde giydikten sonra, bu katedralde de Kudüs ile Ermenistan krallık tacını giyerlerdi. Cami hariminin kuzeydoğu duvarındaki mezar 1365 yılında zatürreden ölen Piskopos Itier de Nabinaux’a aittir.
Osmanlı’nın Mağusa kuşatması sırasında top atışlarıyla hayli zarar gördüğünden, kentin ele geçirildiği 1 Ağustos 1571 tarihinden sonra Sinan Paşa’nın emriyle, mihrap ve minber eklenerek camiye çevrilmiş ve Lala Mustafa Paşa’nın 17 Ağustos 1571 Cuma günü II. Sultan Selim’in adına burada okuttuğu hutbeyle ibadete açılmıştır. Caminin kuzey batı köşesindeki minare, II. Selim’in 1 Mayıs 1572 tarihli buyruğuyla yapılmıştır. Yıldırım isabetiyle tehlike arz ettiğinden 1930 yılında orijinal çan kulesine kadar yıkılarak yerine şimdiki 110 veya 115 ayak yüksekliğindeki minare yapılmıştır.
Camiye çevrildiği tarihten itibaren ‘’Küçük Ayasofya’’ (Ayasofya-i Sağır), ‘’Mağusa Ayasofya’sı’’ ve ‘’Büyük Cami’’ adıyla bilinmekteydi. Ancak Kıbrıs Müftüsü Mehmet Dana Efendi’nin 14 Ağustos 1954 tarihinde aldığı bir kararla adı Lala Mustafa Paşa Camisi olarak değiştirilmiştir. Planlı, üç sahınlı bazilikal tiptedir. Güneydeki sahında Osmanlı ilavesi olan iki mihrap ile bir minber bulunmaktadır.
Bir zamanlar caminin çevresinde, Mağusa’nın fethi sırasında şehit olanların gömülü olduğu bir mezarlık vardı. Bu mezarlık 1928 yılında temizlendikten sonra açığa çıkan ceset kalıntıları sur dışındaki eski mezarlığa taşınmıştır. Mezarlıktan günümüze sadece caminin batı avlusundaki iki türbe gelebilmiştir.
Bunlardan birinin Beni Adnan Kabilesi’nden Şam Müftüsü Es-Seyid Mehmet Ömer Efendi’ye (veya XIX. yüzyılın ikinci yarısında vefat ettiğine inanılan caminin müderrisi İbrahim Efendi’ye) ait olduğu sanılmaktadır.
Tarihi cümbez ağacının bulunan ikinci türbe ise, 22.2.1904 vefat eden Mağusa’lı Mustafa Zühtü Efendi’ye aittir. Caminin hem imamı, hem de hatibi olan Zühtü Efendi, Kavanin Meclisi azası ve Bilal Ağa vakfı mütevellisi görevlerinde de bulunmuştur.
Caminin önünde, Kıbrıs’ta varlığını en uzun süre sürdürebilen büyük bir cümbez ağacı vardır. Bu ağacın 2015 yılı itibariyle703 yaşında olduğu hesaplanmıştır.
