На месте всеградской Михаило-Архангельской церкви находился мужской монастырь, также Михаило-Архангельский, сгоревший 15 июля 1636 г. вместе со всеми строениями прилегавшего к нему деревянного города, основанного в 1584 г. Монастырь после пожара был перенесен за город, а вместо него была построена деревянная церковь в честь Происхождения Честного и Животворящего креста с приделом во имя чуда Архангела Михаила в Хонех, в которой служили сначала монахи. К 20-м годам XVIII в. эта церковь настолько обветшала, что вместо нее, по храмозданной грамоте архиепископа Варнавы от 5.10.1721, было начато строительство новой деревянной церкви с тремя престолами: чуда Архангела Михаила в Хонех, Тихвинской иконы Божией Матери (с южной стороны) и вмц. Екатерины (с левой), освящена в декабре 1722 г. архимандритом Архангельского монастыря Иоасафом.

Церковь сгорела в 1738 г. По храмозданной грамоте архиепископа Варсонофия от 13.10.1742 на ее месте была заложена каменная холодная одноэтажная церковь во имя чуда Архангела Михаила в Хонех с теплым придельным храмом во имя вмц. Екатерины. Екатерининский храм был освящен 30.10.1743 архимандритом Архангельского монастыря Иоасафом, а главный - в апреле 1749 г. архимандритом того же монастыря Леонтием. Четырехъярусный иконостас был оновлен позолотой на средства архангельских купеческих вдов Павлы Михайловны Шингаревой и Екатерины Кирилловны Плотниковой в 1884 г. - к 300-летию г. Архангельска. Иконостас Екатерининского храма замеялся новым 2 раза: в 1832 г. стараниями священника Петра Кутейникова, церковного старосты Михаила Полежаева и городского общества; во второй раз в 1883 г. усердием тех же купеческих вдов, причем старый иконостас, согласно желанию Шингаревой и Плотниковой, был передан в Вологодскую епархию.

В 1769 г. началось строительство другого придельного храма во имя Тихвинской иконы Божией Матери (с южной стороны), освященного 19.1.1771. Этот храм по ветхости был закрыт в 30-х годах XIX в. и вместо него в 1845 г. построен усердием архангельского купца П.К. Куйкина придельный храм в честь первоверховных апостолов Петра и Павла. Этот придел был перестроен в 1883 г. усердием тех же Шингаревой и Плотниковой и освящен 6.6.1883. Прежний иконостас с престолом были пожертвованы в только что построенную церковь в Новодвинской крепости.

Особенно потрудились: церковные старосты купцы Андрей Алексеевич Огапов, состоявшй в этой должности более 25 лет, Михаил Полежаев, Александр Фомин, настоятель церкви о. Петр Кутейников (1803-1851 г.г.), пожертвовавший 1000 руб. ассигн., купец Павел Дудин, построивший каменную колокольню в 1805 г., купец Иван Демидов, пожертвовавший полиелейный колокол в 37 пуд. 30 фун., купец Петр Кутейников, построивший в 1845 г. придельный Петропавловский храм, купеческие вдовы П.М. Шингарева и Е.К. Плотникова, устроившие в 1883 г. новые золоченые иконостасы в придельных храмах, благоустроившие Михаило-Архангельскую церковь и с внешней и с внутренней стороны, Алексей Яковлевич Прозоров, санкт-петербургский купец 1-й гильдии, почетный гражданин, действительный статский советник, и его супруга Антонина пожертвовали полный прибор сребропозлащенных сосудов, весом 5 фун. 2 зол., стоимостью свыше 300 руб.

Церковь считалась бесприходной.

Жертвователи наиболее крупных капиталов: священник Петр Кутейников (293 руб. или 1000 руб. ассигн.), купец Александр Фомин (500 руб.), Казакова (600 руб.), действ. стат. совет. Прозоров (1000 руб.), купеческая вдова Татьяна Рынина (500 руб.), архангельский купец П.К. Кутейкин (350 руб.), потомственная почетная гражданка П.М. Шингарева (200 руб.), купец Василий Костров (1000 руб.), Казаков (100 руб.), Г.П. Ширкин (100 руб.), Ананьин (100 руб.), чиновник Романов (700 руб.). Дом для причта, двухэтажный, деревянный, построен в 1853 г. стараниями церковного старосты А.И. Фомина на пожертвования и церковные средства.

Священники: Варфоломей; Иларион (умер 23.7.1734); Иоанн июнь 1734 г.-апр. 1774 г.; Димитрий Гусев (умер 10.7.1779); Иоанн Безщечкин (умер в 1791 г.); Петр Володимиров; Василий Васильевский и Константин Носов (все вместе служили менее 2 лет); Стефан Ключарев до 1793 г. (закончил семинарию); Стефан Воскресенский до 1.7.1801; Афанасий Рожин 1.7.1801-1803 г.; Петр Иванов Кутейников 1803-17.7.1851 (сын священника); Михаил Щеколдин 1859-1874 г.г.; Аркадий Лысков 1874-1875 г.г.; Афанасий Подосенов 7.1.1876-17.4.1878.