В начале XVIII века Васильевский остров задумывался как центр Санкт-Петербурга. Пётр I желал построить церковь Святого Андрея Первозванного на площади перед зданием Двенадцати коллегий. Это не было реализовано.
Начиная с 1725 года жители Васильевского острова неоднократно выражали желание о начале строительства этого храма. В итоге был выделен участок для строительства - на пересечении Большого проспекта и 6-й линии. По плану архитектора Д. А. Трезини рядом должна была появиться площадь. В 1728 году здесь начали рубить лес, а в 1729-1732 годах была построена деревянная церковь. Её проект, предположительно, составил Карло Джузеппе Трезини. Деньги на её постройку завещал один из первых кавалеров Андреевского ордена - генерал-адмирал граф Ф. М. Апраксин.
В новый храм был перенесён иконостас из дворца князя А. Д. Меншикова, в домовой церкви которого до сооружения Андреевской церкви проходили богослужения для жителей этой части Васильевского острова. В 1744 году церковь получила статус собора. Рядом появилось кладбище, где по преданию похоронили известного государственного деятеля князя Я. Ф. Долгорукого.
Во время грозы 4 июля 1761 года в собор попала молния, деревянное здание быстро сгорело. Иконостас удалось спасти, долгое время он хранился в соседней церкви Трёх Святителей.
Сбор средств на строительство нового здания начался в октябре 1763 года. Крупные суммы пожертвовали Екатерина II и великий князь Павел Петрович. Архитектору А. Ф. Висту было поручено построить каменный храм. Церемония его закладки состоялась 18 июля 1764 года. Спустя два года, когда здание храма было почти завершено, обрушился купол. Архитектора арестовали, однако с него были сняты все обвинения, когда стало доказано, что в обрушении виновато плохое качество кирпича. Постройкой храма продолжил заниматься архитектор Алексей Иванов. Открытие Андреевского собора долгое время откладывали из-за технических неполадок. Это событие состоялось только 21 марта 1780 года. В 1786 году была построена колокольня.
В 1797 году по повелению императора Павла I собор стал орденским храмом святого Андрея Первозванного. Над входом был укреплён знак ордена. В соборе было устроено царское место, купол и алтарь были украшены лепниной. В 1790-х годах была построена часовня.
В 1834 году в соборе было проведено отопление. В 1848-1850 годах по проекту Н. П. Гребёнки к основному зданию были пристроены дополнительные приделы - Успенский и Никольский. На пожертвования купцов В. А. Фролова и А. И. Тименкова иконостас расширили и надстроили одним ярусом. Иконы для иконостаса были написаны художником Н. Г. Шишкиным.
В 1878-1879 годах по проекту А. И. Кракау была перестроена часовня, сооружена ограда, объединившая Андреевский собор с церковью Трёх Святителей.
Андреевский собор был посещаем членами царской семьи. Здесь молились Иоанн Кронштадтский, Ксения Петербургская.
После 1917 года здание было заброшено. В 1920-х годах разобрали южную часть ограды и часовню. В 1938 году церковь закрыли. Здание использовали как склад треста художественно-промышленного производства. При этом нижнюю часть иконостаса закрыли фанерными листами. В 1947-1948 годах здание арендовала Библиотека академии наук, с 1949 года - ЦКТБ-4 Министерства Военно-морского флота. С 1970-х годов здесь размещались фонды Института и музея этнографии АН СССР.
Возвращение прихожанам храма состоялось в 1992 году. 27 мая 2001 года около собора был открыт обелиск в честь кавалеров ордена Андрея Первозванного. В 2003 году по проекту А. А. Казанкова была восстановлена часовня. 10 июля 2007 года в сквере у собора был открыт бюст Ф. А. Головина.
