В 1789 году в Севастополе основалась греческая колония из Анатолийских греков, стремившихся сюда, благодаря большим преимуществам, которыя после покорения Крыма Русское Правительство давало всем, желавшим заселять Таврический полуостров. Эта колония выстроила себе небольшую деревянную церковь во имя Св. Апостолов Петра и Павла, которая некоторое время именовалась также Ахтиарскою — по имени небольшой татарской деревушки, переименованной, по повелению Екатерины II, в город Севастополь.
К 1837 г. Петропавловская церковь пришла в ветхость и ее начали было ремонтировать, как сильная буря разрушила ее вторично. Тогда адмирал Лазарев, страстный любитель древней классической архитектуры, представил на утверждение Императору Николаю I чертеж новаго храма в древне-дорийском стиле, напоминающий храм Тезея в Афинах. В 1839 году началась постройка, а 5 сентября 1843 года новый храм был освящен Преосвященным Гавриилом, архиепископом Херсонесским и Таврическим.
В 1844 году доставлены были заказанныя в Италии художнику Фернандо Пелличио, по образцу статуй Торвальдсена, мраморныя фигуры, изображающия Св. Апостолов Петра и Павла, и установлены в нишах у главнаго входа. В 1848 г., настоятелем Петропавловской церкви был назначен протоиерей Лебединцев, из писем котораго к преосвященному Иннокентию, архиепископу Херсонскому и Таврическому, мы узнаем о судьбах ея во время Крымской войны. Во все время кампании в Петропавловской церкви три раза в неделю совершались службы. Церковь эта, по занимаемому ею возвышенному месту, была более других доступна неприятельским выстрелам, и посещать ее было небезопасно.
19 августа 1855 года, когда городу угрожала неминуемая опасность, и жители покидали его и спешили спасать свое имущество, начальник севастопольскаго гарнизона, граф Остен-Сакен, дал протоиерею Лебединцеву совет выносить святыню и церковную утварь, говоря, что самый город может сделаться вскоре местом сражения, и тогда поздно будет спасать святыню.
20 августа в Петропавловской церкви уже не было служения. Ядро сделало большой пролом в потолке. Утварь и движимость церкви, а также иконы академической живописи были вынесены; иконостас же остался. 25-го августа разбиты были два колокола и повреждена самая колокольня. В конце октября сгорела вся церковь, но колоннада ея уцелела и простояла более 30 лет, до реставрации храма. В ноябре 1887 года, по желанию Императора Александра III, приступили к возобновлению Петропавловской церкви в том самом виде, какой она имела до разрушения, и реставрация, сделанная на собственныя средства С.Л. Кундыш-Володиным и А.А. Максимовым, была закончена в 1889 году.
17 декабря того-же года реставрированный храм был освящен Преосвященным Мартинианом, Епископом Таврическим и Симферопольским.
Источник: Исторический путеводитель по Севастополю / Под редакцией Генерал-Маиора Заиончковскаго. — С.-Петербург, 1907 на сайте «Крымовед — путеводитель по Крыму»
А.М. Зайончковский «Историческій путеводитель по Севастополю»: 1-я часть. Путеводитель по боевымъ и историческимъ местамъ, какъ въ городе, такъ и въ окрестностяхъ: Описаніе историческихъ зданій Севастополя: Петропавловская церковь