Katedraali rakennettiin vuosina 1862–1895. Rakennustyöt olivat keskeytyksissä Kreetan vuosina 1866–1883 olleen turkkilaisia vastaan suuntautuneen kansannousun aikana. Kirkon vihkiminen vuonna 1895 oli suuri kansanjuhla, sillä saari oli edelleen turkkilaisten vallassa, ja kirkkoa pidetään edelleen kansannousun symbolina.[1][2]
Katedraalin vieressä on alkuperäinen, pienempi vuonna 1735 rakennettu Pyhän Menaksen kirkko. Kirkon paikan sanotaan määräytyneen sillä perusteella, että Pyhä Menas oli kerran ilmestynyt siinä eräälle munkille.[1][2]
Rakennus
Katedraali sijaitsee Iraklionin vanhassakaupungissa. Se on yksi koko Kreikan suurimmista kirkoista ja siinä on tilaa noin 8 000 hengelle. Kirkkorakennus on ristinmuotoinen ja siinä on suuri kupoli ja kaksi korkeaa kellotornia. Kirkon pituus on 58 metriä, leveys 38 metriä ja suurin korkeus 32,7 metriä. Kirkon vasen laiva on omistettu Kreetan kymmenelle marttyyrille (Ágioi Déka) ja oikea laiva apostoli Titukselle (Ágios Títos). Sisältä kirkko on koristeltu bysanttilaistyylisillä seinä- ja kattomaalauksilla.[1][2][3]
Kirkon vieressä sijaitsevat myös Kreetan arkkiepiskopaatin rakennus sekä Pyhän Katariinan (Agía Aikateríni) kirkko.[1]