Built as the Cathedral of St. Nicholas, after the Ottoman conquest in 1571, it was turned into a mosque and renamed as the Mosque of St. Sophia. Since 1954 though, it has been known as the Lala Mustafa Pasha Mosque, named after the Ottoman Grand Vizier who led the Ottoman forces in the conquest.

The building is regarded as one of the finest example of the Gothic style in the whole of the eastern Mediterranean. Its construction took upwards of thirty years and it was consecrated as a Roman Catholic cathedral in 1328.

The cathedral was a continuation of the great Frankish Gothic tradition and shares similarities with Rheims Cathedral in France. The Lusignan kings would be crowned as Kings of Cyprus in the Cathedral of Haghia Sophia in Nicosia and then replace to Famagusta to be crowned as Kings of Jerusalem, which was only a ceremonial title, since the Crusaders had lost the Holy Land in 1291.

During the siege of 1570 the cathedral took an immense battering and the walls still bear the pock-marked scars of the cannon balls that the Ottomans spent almost a year hurling at the city. The magnificent twin towers fell to the constant bombardment but, like the walls of the city, the body of the church held fast. As with the conquest of Constantinople, so with Cyprus:-one of the first tasks of the victors was to convert the cathedral into a mosque. This meant the obliteration of all iconography and the removal of all of the statues, stained glass, frescos and paintings. Most of the tombs were emptied including those of the previous kings of Cyprus. No-one knows why the tomb of the Bishop of Famagusta, holding his pastoral staff, was left intact in the north-west corner of the building. As always, a minaret was added in order to facilitate the vital Muslim tradition of calling the faithful to prayer.

The westside triple door is particularly impressive with three huge intricately carved arching porticoes and a beautiful six light window over the central portico.The façade of the cathedral presents an impressive sight from the pedestrianised plaza in front of the building.

The huge ficus sycamores, a kind of tropical fig, in front of the mosque is of some interest. It is reputed to have been planted at the time the building of the cathedral, making it at least 700 years old.