Храм Протата был возведён между 964 и 969 гг. Афанасием Афонским на средства стратига Льва, брата императора Никифора II Фоки, и сохранился до настоящего времени, хотя и претерпел ряд существенных перестроек. Исследователи отмечают, что для этого храма характерно уникальное соединение черт крестово-купольного храма и базилики. Предложенное П. Милонасом объяснение этого феномена как результата перестройки из более ранней трёхнефной базилики в настоящее время опровергнуто в ходе натурных исследований. Исследователи предполагают, что храм Протата упоминается в Житии Петра Афонского, написанном афонским монахом Николаем. В нём говорится о перенесении мощей этого святого «в притвор всечестного храма Всепетой Богородицы, где обычно совершаются ежегодные собрания». Б. Папахрисанфу датирует это Житие 980 г., Андрей Юрьевич Виноградов предлагает более широкую датировку – в пределах Х в. Основное пространство храма (19х16,5 м) – крестообразное, с четырьмя угловыми компартиментами (открывались арками во все рукава креста), отделёнными Г-образными в плане опорами, которым первоначально соответствовали пристенные пилястры. Восточный рукав подкупольного креста и восточные боковые компартименты снабжены неглубокими полуциркульными апсидами. С запада к храму примыкал нартекс (глубина 4,5 м) во всю ширину основного объёма. Таким образом, план постройки представляет собой вариант крестово-купольного храма со столбами и с несколькими изолированными угловыми компартиментами, исследователи находят параллели в таких памятниках, как церковь Пресвятой Богородицы в Скрипу в Беотии (873/874 г.), церковь Епископи в Эвритании (конец VIII – начало IX вв.), константинопольская церковь, известная ныне под названием Атик-Мустафа-паша-джами (IX в.?). При этом исследователи отмечают, что в храме отсутствовал купол: здание было завершено как компактная базилика с трансептом, равным по высоте своду главного нефа или доходящим до основания его свода (по реконструкции Армена Юрьевича Казаряна). При этом положение трансепта на середине центрального нефа и характерная группировка оконных и дверных проёмов на фасадах оставляли впечатление центрического здания с недостроенным или утраченным куполом. Исследователи отмечают, что сложный архитектурный замысел Протата контрастирует с упрощённостью исполнения. Храм имеет ясный, лаконичный и даже несколько суровый облик. Архитектура собора и его конструктивные особенности основаны на местных греческих и балканских традициях. Массивность конструкций, грубоватость кладки с большой долей камня типичны для построек X в. Полуциркульные апсиды и простота деталей также характерны для Балкан, в то время как расположение окон на продольных фасадах в два ряда и их концентрация на торцах рукавов пространственного креста отражают столичную традицию. По разработке стен, свободных и пристенных опор храм Протата выглядит провинциальнее кафоликона Великой Лавры (963 г., реконструкция 1002 г.), возведённого тем же Афанасием Афонским, но в то же время его декор трактован сложнее по сравнению с другими современными греческими постройками, в которых пилоны прямоугольны, а стены лишены пилястр.