Это одно из самых древних строений города, сооружено в 1822 году на средства, пожертвованные вице-адмиралом Ф.Т. Быченским, который в храме и похоронен. В алтаре в свое время имелась медная доска с Иконой Спасителя и текстом: «Здесь погребен вице-адмирал Филипп Тимофеевич Быченский, коим сооружен кладбищенский храм». Церковь крестовокупольная с полуциркульной апсидой в восточной части, увенчана барабаном и куполом с главкой. К храму примыкает крестообразная в плане трапезная. Заканчивается сооружение овальной в плане двухъярусной колокольней, увенчанной шпилем. В западном фасаде находится центральный вход, в южном и северном - еще два боковых. Церковь построена из крымбальского известняка в классическом стиле.
Во время осады Севастополя храм заняли французы и турки, рядом были сооружены их укрепления. Они разграбили церковь и устроили в ней конюшню. Церковь пострадала и от бомбардировок. В Музее севастопольской обороны хранился образ на дереве Архангела Михаила из храма Всех Святых с засевшей в нем картечью.
Церковь восстановлена на средства бывшего церковного старосты Иоанна Пикина, освящена 5 октября 1859 года.