The Church of Crete was reinstated once the Byzantines regained Crete from the Arabs in 961. The ruined town of Chandax was rebuilt from its foundations and became the capital of the island. It was at this time that the church dedicated to Titus the Apostle must have been built, in continuation of the earlier tradition interrupted when the Arabs destroyed Gortyn and the first church dedicated to Titus, parts of which still stand.

The skull of St. Titus and the miraculous icon of the Virgin Mary Mesopantitissa ("of the inner wall") were placed in the new church, along with other relics the Christians had rescued from the church at Gortyn. Byzantine archbishops, Katepano (Supreme Commanders) and generals were buried in the churchyard, in a tradition that was maintained over the following periods.