Строительство каменной церкви было начато по указу Петра I. Царь сам составил рисунок храма, который лег в основу архитектурного проекта. В ХХ веке в качестве автора проекта называли Ивана Зарудного, но документальных подтверждений этому нет. Двухэтажное здание было закончено в 1723 году. Изначально храм с трех сторон окружала узкая обходная галерея на открытых арках. Колокольни не было, но имелась звонница на куполе под высоким шпилем.
Основной объем храма воспроизводит построение нижних ярусов церкви Архангела Гавриила (Меншиковой башни). К центральному четверику с запада и востока примыкают равновеликие объемы притвора и алтаря. Переход к восьмерику осуществлен посредством наклонных треугольных граней. Купол восьмерика увенчан граненым барабаном со шпилем. Декоративная обработка очень скромна и выполнена не вполне профессионально: полукруглые фронтоны-«полуглавия» чрезмерно тяжелы, тонкие пилястры, украшающие четверик, не достигают карниза.
В середине XIX века по сторонам нижней церкви были пристроены два новых придела, образовавшие ныне существующий цокольный этаж, а также была изменена обработка фасадов верхней церкви. Ее первоначальная архитектура восстановлена в ходе реставрации 1960-х годов. Тогда же возле храма была поставлена кованая барочная решетка середины XVIII века от разрушенной церкви Спаса на Большой Спасской улице.
Четырехъярусная колокольня на высоком цоколе, увенчанная главкой со шпилем, построена в 1745—1746 годах и принадлежит совершенно иной эпохе. Сложный силуэт, обилие колонн, разорванные фронтоны и карнизы создают эффектную композицию, резко контрастирующую со скромным убранством церкви. Широкий нижний ярус колокольни с закругленными углами напоминает архитектуру церквей Карла Бланка, что позволяло некоторым исследователям называть его автором проекта колокольни, но к моменту ее постройки К. Бланку было всего 17 лет.