На Кузнечевском кладбище было две церкви. Одна - холодная, деревянная, одноэтажная, в честь Усекновения главы Иоанна Предтечи, построена в 1778 г. военнослужащими Архангельского гарнизона. К середине XIX в. церковь настолько обветшала, что в ней небезопасно было находиться. В 1850 г. церковь была возобновлена, в 1875-1876 г.г. отремонтирована на средства купца Артемия Сергеевича Степанова и вновь освящена 29 августа 1879 г. Сначала церковью заведовал причт Кузнечевской церкви, в 1863 г. был образован самостоятельный приход со своим причтом.

Вторая церковь, теплая, каменная, одноэтажная, в честь св. Андрея Критского и всех святых, построена по завещанию купца 1-й гильдии Андрея Феодоровича Долгошеина его наследницей Александрой Ивановной Кочуровой. Закладка церкви была совершена 17 октября 1840 г. Освящение состоялось 17 октября 1843 г. До 1863 г. церковью заведовал причт Боровской Успенской церкви.

Со времени учреждения прихода из пожертвований складывался церковный капитал (6200 руб. к 1.1.1894), проценты с которого расходовались на содержание церквей, на уплату налогов в пользу духовно-учебных заведений и других епархиальных учреждений.

Приход составляли Елизаветинская мужская богадельня и больница Приказа общественного призрения.