Самым первым храмом, с которого начались раскопки, стала базилика Крузе. Раскопки велись по приказу командира черноморской эскадры и губернатора Севастополя А.С. Грейга. Организация работы была поручена морскому офицеру Г. Крузе, и в результате найденный его экспедицией в 1827 году храм был назван именем этого лейтенанта.
Датой его постройки первоначально считали IV-V века, однако в результате раскопок 2013-2014 гг. в культурном слое храма была найдена монета императора Юстиниана (527-565), что позволяет говорить о постройке храма в VI веке. Стены базилики сохранились на небольшую высоту. Храм представлял собой большую трехнефную базилику (26х18 м) с редкой триконхиальной (трехлепестковой) формой апсиды. Длина алтарной части достигала до 7 метров, диаметр боковых экседр (апсид) — 3 м, центральной апсиды — 6 м. Боковые нефы достаточно узкие: в среднем 2,8 м. Ширина центрального нефа — 8 м. Перед входом в нартекс (притвор) сохранились две вырубленные в скале ступеньки, ведущие в храм с улицы. С улицы в нартекс (притвор) вели два входа: кроме главного, был еще боковой левый. Базилика была сложена из больших тесаных известняковых блоков. В притворе базилики находились гробницы, высеченные в скале. Пол был покрыт мраморными плитами.
Г. Крузе не закончил раскопки из-за начавшейся в Севастополе эпидемии чумы. При доследовании, проведенном более чем через полвека, внутри базилики было найдено большое количество обломков мраморных плит алтарной преграды, украшенной крестами, резные капители колонн и карнизы, обломок мраморного голубя, остатки греческой надписи, монеты императоров V-VI и IX-XI вв. Храм просуществовал примерно до рубежа X-XI века, затем на его месте был устроен некрополь.