К концу июля 1801 г. был вырыт котлован под здание, затем забито 1800 деревянных свай, уложены тосненская плита под стены и гранитные блоки под опорные столбы. К 1803 г. был сделан гигантский фундамент глубиной около 8,5 м и объёмом 32,5 тыс. куб. м. Тогда же приступили к сооружению цоколя и кладке кирпичных стен подвальных помещений. Каменными работами руководили М. Руджи и Д. Руска. В 1805 г. под Выборгом были вытесаны, в основном, из монолитов розового финляндского гранита-рапакиви 56 гранитных колонн для интерьера высотой 10,7 м (мастер Ксенофонтович Суханов; бронзовые капители отлиты на заводе Чарльза (Карла Николаевича) Берда). Гранит-рапакиви послужил также материалом для входных лестниц и пола. Для цоколя собора, колоннады и постаментов использовали серый сердобольский гранит. Стены снаружи облицованы пудостским пористым известняком, из него изготовили колонны наружной колоннады, барельефы и элементы декора фасадов. К сентябрю 1805 г. здание было возведено до карниза, до конца года были установлены колонны внешней колоннады. В 1808 г. начались и работы по внутренней отделке собора; лепной декор выполнили Б. Медичи и Ф. Торричелли. Тёплый нежно-розовый тивдийский мрамор (современный Кондопожский район, Карелия) использовался в Казанском соборе в декоративной отделке пола, царского места и амвона, их цоколь – из ювенского мрамора (Приладожье), декор и мемориальные доски – из шокшинского кварцита (Прионежье, Карелия). В тех же краях добывались шунгитовые сланцы (из них были сделаны полы, подоконники, выполнен декор амвона и царского места). Четыре колонны иконостаса, внутренняя балюстрада, плиты для облицовки аттика изготовлены из ревневских яшм, добытых на Алтае, близ современного города Змеиногорска. В 1809–1810 гг. в соборе были установлены колонны. Значительное превышение сметы заставило к 1809 г. принять решение не золотить базы колонн, не устанавливать гранитные фигуры апостолов Петра и Павла, замыкающие западную ограду (сделали только постаменты), колоссальные бронзовые статуи архангелов Михаила и Гавриила по краям северной колоннады на аттик и т.д. 7 апреля 1807 г., сразу после смерти И.Е. Старова, его место в комиссии занял А.Н. Воронихин, а надзор за строительством был поручен Джакомо Антонио Кваренги. Вскоре после того как 27 июля 1811 г. сломали старую церковь, император приказал графу А.С. Строганову завершить строительство. В 1810 г. за возведение храма А.Н. Воронихин получил орден св. Владимира четвёртой степени и пожизненную пенсию, в 1811 г. – орден св. Анны второй степени. Инициатор проекта граф А.С. Строганов удостоился чина первого класса. Простудившись на освящении собора, он через 2 недели скончался (27 октября 1811 г.). А.Н. Воронихин умер 23 февраля 1814 г., на его надгробии на Лазаревском кладбище было помещено изображение собора. Руководителем работ в соборе с 1 июля 1814 г. стал профессор Андрей Алексеевич Михайлов. 24 августа 1818 г. строительная комиссия была закрыта; новая комиссия по доделке собора работала с 26 сентября 1818 г. по 3 мая 1827 г. А.Н. Воронихин (как и другие конкурсанты) первоначально собирался создать центрический храм, имевший в плане греческий крест, но затем обратился к форме трёхнефной базилики.