Once the Venetians had settled on Crete, the Vatican removed the Orthodox Archbishop and Bishops of Crete and installed Catholic prelates. Yet the new rulers left the Church of St. Titus untouched, with its Byzantine icons and Orthodox relics. In an attempt to give the impression that they were maintaining Cretan ecclesiastical tradition, on occasion they would even allow Orthodox priests to conduct Eastern rite services.

Having suffered extensive earthquake damage, the church was renovated in the mid 15^th century by Catholic Archbishop Fantino Dandolo. The skull of St. Titus was placed on the high altar together with the relics of St. Stephen, St. Martin and St. Fotini. The re-consecration ceremony took place on 3^rd Jaunary 1446.

The church survived another earthquake in 1508 without losing any of its original grandeur, but suffered irreparable damage in a fire on 3^rd April 1544. In 1577 it was rebuilt once more, to become the "most beautiful basilica of old times" (pulcherrima et vetustis operis basilica), in the words of traveller Jan Van Kootwyck (1598).