The church inaugurated by Fantino Dandolo in 1446 was an elaborately decorated three-nave basilica with a timber roof. Three doors in the west facade appear on a plan by the artist Georgios Klontzas.

The fifteenth-century building was destroyed in an earthquake in 1856, and rebuilt in 1869 to plans by Athanassios Moussis, an architect from Epirus. The imposing new church was built along eclectic lines. "This graceful architectural work of art is without parallel on Crete," as the Heraklion scholar Stephanos Xanthoudidis puts it. "As seen today, its numerous windows with their curved and arched frames lend it an Arabic aspect."

Almost a perfect cube, St. Titus is built in the form of a single-roofed domed basilica with a free standing bell tower in the southwest corner. The church is without apses and faces east. The interior is divided into three naves by two rows of arches.