В 1805–1817 гг. вместо обветшавшего деревянного здания один из лучших петербургских архитекторов Андреян Захаров возвел в Кронштадте, на Андреевской улице, каменный собор св. апостола Андрея. Церемонию закладки 20 июня 1805 г. в присутствии императора Александра I освятил Санкт-Петербургский митрополит Амвросий (Подобедов). Торжества происходили как грандиозный праздник с салютом военных кораблей, в память о закладке храма отчеканили золотую медаль. Освящение собора совершил 26 августа 1817 г. епископ Ревельский, впоследствии митрополит Московский, святитель Филарет (Дроздов).
В Андреевском соборе 53 года служил великий молитвенник земли русской, св. праведный Иоанн Кронштадтский (с декабря 1855 по декабрь 1908 г.). Одной из главных святынь храма был золотой крест с частицей мощей св. Андрея Первозванного, находившийся в киоте храмовой иконы апостола Андрея. Не менее почитаемым был резной костяной медальон-образ св. Андрея Первозванного, вырезанный самим Петром Великим и подаренный им в первый деревянный собор. В этом соборе отмечались многие важные события государственного значения.
В других храмах Кронштадта также хранились реликвии, связанные с апостолом Андреем. Так, в Морском Богоявленском соборе находился принадлежавший Петру I небольшой золоченый с эмалями крест св. Андрея Первозванного на белом круглом медальоне и при нем – голубая орденская Андреевская лента, принадлежавшая императору и подаренная в храм после его смерти. О взятии г. Очакова в 1737 г. напоминал образ св. апостола Андрея «с деяниями» в серебряном позолоченном окладе, переданный в Богоявленский собор контр-адмиралом Я. С. Баршем в 1742 г. В церкви св. князя Александра Невского при кронштадтском Доме трудолюбия почиталась икона св. апостола Андрея, по преданию, написанная для первоначального Андреевского собора. Ее военная история связана с сербо-черногорско-турецкой войной 1876 г., так как образ в тот период находился при врачебно-санитарном отряде, выезжавшем из Кронштадта на помощь сербам.
Помимо кронштадтского Петр I задумал построить соборный храм апостола Андрея на стрелке Васильевского острова (перед зданием Двенадцати коллегий), где планировал создать центр своей новой столицы Санкт-Петербурга. За год до кончины, в 1724 г., император заказал проект этого храма известному шведскому архитектору Никодемусу Тессину-младшему. Зодчему было поставлено условие: храм должен напоминать римский собор св. Петра и иметь в длину 427 футов (130 метров). В 1725 г. Тессин представил проектные чертежи собора; была изготовлена его модель, но осуществить замысел не удалось из-за скоропостижной кончины императора.
В январе 1727 г. императрица Екатерина I – «первейшая Великая Магистра ордена святаго апостола Андрея кавалеров Российских» именным указом распорядилась отпустить 3 тыс. рублей для возведения церкви апостола Андрея на выделенном участке Васильевского острова (на углу Большого проспекта и 6-й линии). В том же году началась подготовка к строительству храма, которое частично осуществлялось на пожертвования кавалеров ордена cв. апостола Андрея.
В 1729 г. архиепископ Нижегородский Питирим освятил закладку деревянного однопрестольного храма, построенного по проекту архитектора Джузеппе Трезини и освященного после окончания строительства 8 октября 1732 г. во имя апостола Андрея «для торжества и праздников кавалеров Андреевского ордена». Освящение храма совершил сподвижник Петра Великого архиепископ Новгородский и Великолукский Феофан (Прокопович) – духовный пастырь кавалеров ордена.
Иконостас в новый храм перенесли из домовой церкви петербургского дворца А. Д. Меншикова, средства на облачения и утварь пожертвовала императрица Анна Иоанновна. 4 февраля 1744 г. Андреевскому храму по распоряжению императрицы Елизаветы Петровны и решению Святейшего синода присвоен статус собора. Новый каменный собор был заложен 18 июля 1764 г. по проекту архитектора А. Ф. Виста, но 6 августа 1766 г. во время сооружения сводов купола неожиданно рухнули, за что зодчего посадили под арест. Строительство продолжалось, вероятно, по проекту выпускника Академии художеств архитектора А. А. Иванова и в 1768 г. было в основном завершено. Однако собор был полностью освящен только 23 марта 1780 г., и в 1797 г. повелением императора Павла I официально назначен орденским, кавалерским, в связи с чем над входом был установлен барельеф с изображением ордена апостола Андрея Первозванного, который несут два ангела.