With the recovery of Crete from Nikiforos Fokas, the seat of the bishopric is transferred from Gortyna to Chandakas, which became the capital of the island. The new cathedral, which is the most established and largest in the city, is dedicated to the Apostle Titos. Here, amongst other relics, there are gathered the Holy Skull of the Apostle and the miraculous icon of Messopapaditissas. When the Venetians took over Crete, they installed in the orthodox bishop the Latin archbishop, converting by that the church of St. Titos into a Latin bishop.

In the middle of the 15th century, the Latin archbishop, F. Dandolo is renovating the church. Other distractions, caused by earthquakes and fire, resulted to the rebuilding of the church from the start around 1557. The church was a basilica, almost square in shape, with a dome in the middle and a bell-tower in the southwest corner. The church from the inside was divided in three aisles with two series of columns. During the Turkish period, the church was given to Fazil Ahmet Kioprouli and it was changed into a mosque, while the bell - tower was tranformed into a minaret. The big earthquake of 1856 destroyed the temple which is being, once more, rebuilt. After the exchange of populations, the Church of Crete repaired it accordingly, and in 1925 it was dedicated again to Apostle Titos. East of the church there was the building of the archdiocese.