W latach 1063-1094 kościół został odbudowany. Budowla wzorowana na konstantynopolskim kościele św. Apostołów (używana jest także nazwa kościół Dwunastu Apostołów) została zaprojektowana w stylu bizantyjskim na planie krzyża greckiego z pięcioma kopułami rozmieszczonymi nad nawami w ramionach krzyża i nad polem w przecięciu się naw. Konstrukcja czasz przypomina rozwiązania architektury islamu. Podobne kopuły wykonano nad meczetem Umara w Jerozolimie i nad mauzoleum dynastii Fatymidów w Kairze.
Fasada była wielokrotnie rozbudowywana i przebudowywana. Po 1204 dobudowano narteks otaczający ramię wejściowe kościoła. Zgodnie z życzeniem doży Domenico Selvo, każdy statek wenecki zobowiązany był do przywożenia darów służących ozdobie nowej świątyni. Stąd różnorodność stylistyczna wielu detali architektonicznych pochodzących z różnych miejsc i wykonanych na przestrzeni długiego czasu. Mimo wszystko kościół zachował swój pierwotny styl.