Собор назван в честь одного из самых почитаемых в христианстве святых — Святого апостола Андрея, архиепископа Константинопольского. Византийская церковь почитает его с именем «Протоклетос». Андрей родился в 5-10 г.г. нашей эры в Галилее, вместе с братом Петром были рыбаками на побережье Галилейского моря. Там на побережье они встретили Его и это им Иисус адресовал знаменитое изречение, что они будут «ловцами человеков». Согласно Евангелию от Иоанна, Андрей Первозванный был первым призван Иисусом Христом в качестве ученика.
За год до своей смерти, набожный император Петр I решил строить Андреевскую церковь на стрелке Васильевского острова. Петр с присущим ему размахом, хотел чтобы церковь была не меньше, чем собор Святого Павла в Лондоне. Чертежи для такого проекта осуществлял шведский архитектор Никодемус Тессин-младший. Поручил строительство храма Петр I своему соратнику графу Федору Апраксину, который в том числе ведал сбором пожертвований. После смерти Петра I в 1725 году, было определено новое место для строительства на углу Большого проспекта и 6 линии Васильевского острова. В то время это было место, заросшее лесом. Получив разрешение от Синода на строительство знаменитый Джузеппе Трезини в период 1729-1731 г.г. осуществил строительство деревянной церкви на каменном фундаменте на этом месте. В первое время при церкви было устроено кладбище, на котором были похоронены генерал, князь Яков Долгоруков, а также невеста Петра II княгиня Екатерина Долгорукова. При Анне Иоанновне из другой церкви сюда был перевезен иконостас и 8 октября 1732 года церковь была освящена архиепископом Феофаном во имя Святого апостола Андрея Первозванного. Однако, за год до смерти императрицы Елизаветы Петровны, в 1761 году деревянный собор постройки Трезини в результате попадания молнии сгорел до основания.
Строительство нового каменного храме уже происходило при императрице Екатерине II в 1764 году. Новым архитектором проекта был академик Алексей Иванов. Большая часть денег для строительства поступила от императрицы Екатерины II (2 тысячи рублей), от дворян и будущих прихожан, а также от цесаревича Павла. Закончено строительство нового трехпридельного каменного Андреевского собора было к марту 1780 года. Особое внимание прихожан обращено к 17-метровому трехярусному, резному иконостасу в стиле Растрелли. По содержанию и качеству исполнения он напоминает иконостас Петропавловского собора.