Самым древним храмом Херсонеса, по всей видимости, была Восточная базилика, находившаяся в самом конце главной улицы. Ее строительство связывают с именем одного из херсонесских святителей — святого Капитона.
Св. Капитон, прибыв в город, убеждал приверженцев язычества, собравшихся у стены города, принять христианскую веру. Язычники предложили епископу продемонстрировать силу Бога: «Если тебя, вошедшего в одну из печей, не сожжет огонь, то мы уверуем в проповедуемого тобою Бога», то есть обязались креститься, если епископ войдет в печь для обжига извести и пробудет там условленное время. Епископ выполнил условие, «сотворив молитву, по возглашении диаконом “вонмем”, тотчас вступил в печь, оградив себя оружием креста, и пробыл в ней довольное время, молясь и шевеля устами, о чудо! Затем, вложив в лоно уголья, он вышел невредимым силою Духа». Пылкая проповедь святого и чудо, свершенное по его молитве, привели к крещению горожан и возведению на месте языческого комплекса церкви в честь св. апостола Петра.
Тексты житий сообщают о строительстве церкви: «повелев тотчас построить крещальню из обожженной извести, всех окрестил в ней […] воздвиг он и храм, примыкающий к ней, во имя первого и верховного из апостолов Петра». Скорее всего, христиане разобрали античные языческие храмы на территории Восточной площади и положили начало формированию нового христианского культового комплекса. Он изначально уже включал в себя церковь и баптистерий. Фрагменты античных построек могли быть использованы для возведения христианского храма, что в значительной степени могло способствовать ускорению процесса.
Принято считать, что церквей было две: ранняя и сменившая ее поздняя базилика, остатки которой сохранились на площади и сегодня. Действительно, известны находки, которые могут быть отнесены к раннему периоду существования христианского комплекса. Среди них три плиты. Первая была открыта на территории Херсонесского некрополя. На ее лицевой стороне в рамке изображен Христос — безбородый юноша с нимбом, подающий руку тонущему Петру. В настоящее время плита хранится в Санкт-Петербурге, в Государственном Эрмитаже.
Вторая, так называемая «Парижская плита», хранится в Лувре. На лицевой стороне, в рамке, изображен Христос в виде безбородого юноши с нимбом, протягивающего правую руку в жесте благословения.
Существует и третья плита — херсонесская. Она была найдена близ Восточной базилики. На ее лицевой стороне видна верхняя часть рамки, а под ней — следы изображения головы. Сохранившийся фрагмент текста расшифровывается как «Господь Иисус…» Ученые датируют эти памятники концом IV — началом V в. Несомненно, все три плиты принадлежали одному литургическому устройству. Сохранившиеся сюжеты связаны с морской и водной тематикой. Допустимо предположение о возможной принадлежности плит ограде крещальной купели.
Таким образом, в Восточной части Херсонеса в конце IV в. начал формироваться христианский комплекс, связанный с почитанием апостола Петра. Он состоял из базилики с нартексом и экзонартексом, крестообразной усыпальницы, баптистерия и вспомогательного помещения. Сохранившиеся фундаменты базилики историки датируют по-разному, от конца IV — начала V в. до конца VI — начала VII в.
Базилика была построена на скальном основании и представляла собой трехнефное сооружение, с мозаичными полами, облицованное внутри мраморными плитами. Размеры в плане составляли 34,6×16,4 м. С северной стороны к базилике была пристроена крестообразная усыпальница. В усыпальнице было открыто несколько могил. Скорее всего это было место погребения мирян — ктиторов храма апостола Петра.
Сооружение имело сводчатое перекрытие, высота строения составляла около 6 м, толщина стен — 0,98 м, длина и ширина ветвей составляла 4,9 м. Усыпальница имела три входа, с западной стороны: один в западной ветви креста, два других — в южной и северной ветвях.
Церковь просуществовала до Х века.