Планом 1836-1839 годов к городу с юга, между Всесвятским кладбищем и Крестовоздвиженским монастырем была прирезана значительная территория бывших выгонных земель. К 1856 году она оказалась заселена, хотя жители по старинке считались прихожанами отдельных Всесвятского и Покровского храмов. Поэтому они просили построить среди их дворов новую церковь в честь Трех российских святителей: Петра, Алексея и Ионы.

По указу нижегородского военного губернатора Ф.В.Анненкова поиском места для возведения церкви на пересечении Немецкой и Канатной улиц занялся Н.А.Фрелих. У солдатки Степановой и мещанки Незарушкиной были куплена за 30 и 60 рублей соседние участки земли. На месте будущего храма в 1856 году поставили каменный столб с голубцом для иконы. Ко всем нижегородцам обратились с просьбой о пожертвованиях на строительство.

Городовой архитектор Н.И.Ужумедский-Грицевич разработал проект церкви. Он был рассмотрен в декабре 1856 года, получил замечания, доработан, в 1857 году вновь рассмотрен Нижегородской строительной и дорожной комиссией и 29 июля 1858 года одобрен Синодом.

Возвести каменный пятиглавый Трехсвятксий храм с колокольней (16х7 саженей) подрядился купец III гильдии Лука Максимович Коптев. В апреле 1859 года он сообщал Нижегородскому епископу Антонию, что материал заготовлен, рабочие наняты, но не отбиты линии для закладки фундаментов и не назначен архитектор для надзора за строительством. 28 апреля 1859 года Строительная и дорожная комиссия назначила архитектором автора проекта Н.И.Ужумедского-Грицевича.

24 июня 1860 года в Синод сообщалось, что церковь "кладкою окончена", хотя внутри еще ставили иконостасы, белым камнем выстилали полы, закупали колокола (Большой - 103 пуда, Полиелейный - 51, Вседневный - 20, всего 7 колоколов).

На строительство церкви было потрачено 30750 рублей. 11 декабря 1860 года "при многочисленном стечении народа" Нижегородский епископ Нектарий освятил главный престол, 14 и16 декабря - приделы. Внутренняя же отделка продолжалась до 1863 года, когда были расписаны своды, а иконостасы вызолочены.