В 1799 году Павел I объявил конкурс на строительство нового собора в честь иконы Казанской Божией Матери. Прообразом нового храма стал собор Святого Петра в Риме: Павел I сам бывал в столице католического мира и был восхищен красотой этой базилики. Храм строился не на пустом месте, он должен был заменить обветшавшее здание Казанского храма, где когда-то венчались родители Павла I и где Екатерина II получила благословение духовенства в день дворцового переворота 1762 года. Архитектором был назначен Андрей Воронихин, бывший крепостной и протеже графа Александра Строганова, возглавлявшего Академию художеств. Оба считали строительство крупнейшего на то время православного храма на главной улице императорской столицы делом своей жизни.
Собор был окончен в 1811 году и вскоре стал восприниматься современниками как символ воинской славы и победы над Наполеоном. Сюда привозили трофеи – знамена, штандарты и ключи от взятых городов, а в 1813 году здесь был похоронен фельдмаршал Кутузов, умерший в Заграничном походе русской армии. Довершила идею храма-триумфа установка в 1837 году памятников Кутузову и Барклаю де Толли. У ног главнокомандующих лежат французские знамена с переломленными древками. Храм стал важнейшей новой достопримечательностью города и его обязательно осматривали гости столицы. Именно в Казанский собор отправляется на молебен отделившийся от майора Ковалева Нос в одноименной повести Гоголя. Во время богослужения Ковалев пытается объясниться со сбежавшей от него частью тела, но безуспешно. Цензуре эта сцена не понравилась и показалась неприличной, поэтому в прижизненном издании Гоголю пришлось перенести сцену встречи из храма в соседний Гостиный двор.