Церква Всіх Святих стоїть усередині Миколаївського некрополя й належить до найдавніших міських храмів. Її заклали 1807 року за клопотанням головного командира Чорноморського флоту адмірала Івана де Траверсе, а вже 1808-го освятили. Кошти давали нижчі чини морського відомства, адміралтейські служителі, купці, міщани та інші жителі міста.
Хрестоподібний храм і перебудова
Основою споруди стала одноповерхова кам’яна будівля у формі хреста з дзвіницею над входом. Така композиція відрізняє храм від пізніших великих соборів: головний силует тут створюють простий об’єм, центральна баня та невисока вхідна вертикаль.
У 1858 році церкву перебудували й розширили за участі міського голови та колишнього церковного старости Костянтина Соболєва. Саме 1858 роком споруду датує сучасний охоронний облік. У ньому враховано не тільки первісне заснування, а й той архітектурний етап, який визначив пізніший вигляд будівлі.
Огорожа, дзвін і каплиця
Наступний помітний шар з’явився 1876 року. Стараннями церковного старости Івана Бартенєва та за підтримки Миколи Аркаса територію обнесли чавунними ґратами, встановили новий дзвін, а в огорожі спорудили двоповерхову каплицю. Так біля самого храму виник окремий меморіальний об’єм, пов’язаний із родиною Аркасів.
Каплиця-склеп, споруджена 1881 року в стилі італійського ренесансу, зберігає родинну пам’ять Миколи Аркаса — історика, композитора й автора опери «Катерина». У жовтні 2001 року відремонтовану каплицю знову освятили. Вона є частиною некрополя, але не тотожна самій церкві.
Храм у просторі старого кладовища
Старе міське кладовище позначене вже на плані 1795 року. Некрополь формувався на східній околиці військової слободи, а церква з’явилася тут як релігійний осередок для поховального простору, що існував раніше. Поруч збереглися могили, склепи та пам’ятні об’єкти різних періодів, тому архітектуру храму важливо розглядати в ширшому меморіальному середовищі.
Міський путівник окремо наголошує, що церкву не закривали владою і вона зберегла первісну архітектурну основу. Напередодні двохсотріччя храм реставрували, оновили ікони й позолочені куполи. Охоронний перелік нині фіксує церкву як пам’ятку архітектури, не змішуючи її з численними окремими похованнями та меморіалами некрополя.