В сквере, примыкающем к Советской (ранее Чесменская) улице, находится один из самых значительных сохранившихся памятников культового зодчества - храм во имя святых апостолов Петра и Павла. Расположен на месте обветшалой деревянной церкви, построенной в 1792 году анатолийскими греками. Когда же в 40-е годы XIX века архитектор Джон (Иван Иванович) Уптон спроектировал планировку холма, М.П. Лазарев пожелал соорудить здесь монументальный храм в древнегреческих традициях. Проект разработал инженер-подпоручик морской строительной части В.А. Рулёв. Строили его с 1839-го по декабрь 1844 года из инкерманского камня и сарматского известняка, но освятили храм уже 5 сентября 1843 года. Установлен на высоком стилобате с 44 каннелюрованными колоннами дорического ордера по периметру здания. На восточном фронтоне помещен скульптурный рельеф - Всевидящее око. Главный и западный фасады завершены треугольными фронтонами, которые ранее венчали кресты. При разработке проекта храма В.А. Рулёв использовал приёмы античного зодчества. Некоторые считают, что прототипом его послужил собор Гефеста в Афинах, хотя они существенно отличаются друг от друга.

У входа в храм в 1844 году установили мраморные статуи в натуральную величину апостолов Петра и Павла, копии работ скульптора Б. Торвальдсена, созданные им для города Каррары. Статуи для севастопольского храма выполнил итальянский мастер Фердинанд Пеличчио (Пелличио). В Крымскую войну в соборе Петра и Павла совершалось богослужение практически до конца обороны города настоятелем протоиреем Арсением Лебединцевым. Храм был полуразрушен, статуи вывезены по указанию маршала Пелисье в Константинополь и установлены в часовне здания французского посольства. Возобновлен в первоначальном виде только в 1889 году на средства мецената С.Л. Кундышева-Володина и подрядчика А.А. Максимова, освящен 17 декабря. Во время второй мировой здание получило незначительные повреждения. Закрыт для богослужения в 1931 году. До войны в нем находился городской архив, с 1946 по 1957 год - театр им. А.В. Луначарского, затем - Городской дом культуры. В настоящее время принято решение о передаче храма общине.