Ранние хроники сообщают, что церковь IX в. сильно пострадала во время большого пожара в 976 г. Однако реставрационные работы при доже Пьетро Орсеоло, завершенные в течение всего лишь двух лет, указывают на то, что здание не могло быть полностью разрушено. Реставрация, похоже, была достаточно вольной, так как уже в середине XI в., менее чем через 100 лет, было решено перестроить храм еще раз, на этот раз более радикально, с более масштабным размахом. Окончательная же реконструкция, которая продолжалась во время правления трех дожей, была начата при доже Доменико Контарини (1042–1071) и завершена при доже Витале Вальере (1086–1096).
Чтобы представить себе Сан-Марко в том виде, в каком он был в IX в., историк архитектуры должен положиться на археологию. Однако внешний вид церкви XI в. можно относительно легко реконструировать по виду нынешнего здания. Необходимо, прежде всего, большое усилие воображения, чтобы стереть из памяти обилие мозаики, прекрасного мрамора и витиеватой скульптуры на крышах, которые теперь ее украшают – и в значительной степени скрывают этот великий венето-византийский памятник.
Деревянный купол был заменен пятью огромными куполами с кирпичными сводами, что было смелым решением ввиду нестабильности венецианской почвы, и что с тех приводит к проблемам, связанных с их конструкцией. (Флорентийский архитектор Якопо Сансовино впервые прославился в Венеции, когда в 1527 г. успешно отремонтировал купола, окружив их железными кольцами.) Чтобы представить эти пять кирпичных куполов, мы должны попытаться мысленно лишить Сан-Марко одного из его наиболее запоминающиеся черт, а именно высоких куполов, покрытых свинцом и завершенных фонарями в форме луковиц, которые теперь венчают церковь. Эти живописные купола – просто внешние оболочки, добавленные в XIII столетии, чтобы сделать горизонталь церкви более заметной и намекнуть на александрийское происхождение святого. Этот более плоский тип купола более типичен для византийских церквей Константинополя и Греции, откуда и черпали вдохновение строители Сан-Марко.
Чтобы выдержать лишний вес кирпичных куполов перестройки XI в., стены пришлось значительно утолщать. Церковь также была расширена как с северной, так и с южной сторон: на севере, чтобы укрепить остатки часовни Сан-Теодоро начала IX в., которая была окончательно снесена в это время; на юге, чтобы включить то, что, вероятно, было угловой башней старого Палаццо Дукале и которое теперь составляет часть сокровищницы Сан-Марко. На западном конце был добавлен нартекс, а на востоке были построены две меньшие апсиды по обе стороны от главного пресвитерия. (Баптистерий на южной стороне и соответствующая пристройка к атриуму на севере предположительно датируются XIII в.)
Как и в Санта-Фоске, которая также была построена как капелла-реликварий, для размещения мощей святого был выбран византийский крестообразный план. Выбор греческого креста прочно ставит Сан-Марко в один ряд с другими апостольскими церквями. План действительно очень похож на церковь Святых Апостолов (Апостолион) в Константинополе, перестроенную императором Юстинианом в VI в. Этот знаменитый византийский памятник больше не существует, поскольку он был разрушен после захвата Константинополя османами в 1453 г. Она известна по иллюстрации в манускрипте в Париже, по ее письменным описаниям, а также по предполагаемому сходству с современной апостольской церковью св. Иоанна Богослова в Эфесе. Даже в тех частях Италии, которые были связаны с Западной Церковью и, таким образом, были оторваны от византийских традиций, именно крестообразные планы традиционно выбирались для апостольских церквей, таких как церковь святых апостолов в Милане, основанная св. Амвросием в 382 г. О том, что о своем святом покровителе венецианцы думали именно как об одном из апостолов, свидетельствует их жадное собирание святых мощей других апостолов, многие из которых до сих пор хранятся в Сан-Марко.
Каждое куполообразное пространство, по сути, образует отдельный греческий крест меньшего масштаба с четырьмя цилиндрическими сводами, распределяющих нагрузку купола. Преобладание общего плана греческого креста подчеркивается тем, что аркады отгораживают вспомогательные цилиндрические сводчатые пространства, которые также служат опорой для галерей. Нынешние приподнятые дорожки – это остатки первоначальных галерей. Кажется, что когда-то они были намного шире, как те, что сохранились на концах обоих трансептов и в западной части нефа, но впоследствии были сужены, чтобы пропустить больше света в проходы под ними. Существующие галереи ясно свидетельствуют об этом изменении, так как внешние балюстрады выполнены в массивном византийском стиле с рельефными панелями, а внутренние – типично готического стиля с рядами тонких колонн. Причиной переделки, должно быть, было загромождение многих верхних окон, чтобы обеспечить дополнительное пространство на стенах для мозаик, из-за чего в церкви было слишком темно.