В 1728 году на Васильевском острове, на пересечении Большого проспекта и 6 линии, был выделен земельный участок, на котором возвели деревянную церковь. Предполагаемым автором проекта был Д.А. Трезини. Церковь была освящена во имя Святого Апостола Андрея Первозванного в 1732 году и предназначалась для торжества и празднества кавалеров Андреевского ордена. В 1744 году церковь получила статус собора.

На торжественных богослужениях в церковь приходили члены царской семьи, многие известные личности того времени. В их числе М. Ломоносов и В. Тредиаковский. С 1740 по 1745 годы рядом строится другая церковь по проекту Дж. Трезини. Освящение состоялось в 1760 году во имя Трёх Святителей Вселенских. Помещения церкви Трёх Святителей использовались в основном для ризницы Андреевского собора, церковной библиотеки и архива.

4 июля 1761 года деревянный храм сгорел во время грозы. 18 июля 1764 года был заложен новый храм под руководством А. Виста. Именно он сохранился до наших дней. Строительство было завершено к 1780 году. Открывшийся храм стал центром кавалеров ордена святого Апостола Андрея Первозванного. В 1786 году была построена колокольня, а в 1790 году – часовня. В 1797 году над входом установили барельеф с изображением ордена Андрея Первозванного, которого несут два ангела.

Во второй половине XIX века при храме начало действовать «Общество вспоможения бедным», со временем ставшее крупнейшим в России приходским благотворительным обществом.

После революции храм пришёл в упадок, затем был разграблен и закрыт. Здание использовали как склад.

В 1928 году с колокольни сняли колокола, передали их в Петропавловскую крепость, а впоследствии переплавили. В дальнейшем здание арендовали различные учреждения. Во время Великой Отечественной войны пострадали фасады, крыша, иконостас, интерьер. В 1992 году храм был отреставрирован и возвращен верующим. Также была возвращена и церковь Трех святителей. До наших дней в соборе сохранился великолепный резной деревянный 17-метровый золоченый иконостас XVIII века, один из старейших в городе.

В 1995-1996 годах на купола храма установлены позолоченные кресты. В 2001 году в честь 300-летия учреждения ордена Андрея Первозванного перед храмом был установлен обелиск. В 2007 году в сквере у храма был открыт бюст Ф.А. Головина.

Богослужения в церкви проводятся каждый день.

Настоятель - протоиерей Михаил Мокрополов.