Начало распространения православия на территории современного Северного Казахстана было положено возведением Российской Империей на юге Западной Сибири военных укреплений, входивших с состав так называемых Сибирских пограничных линий. Сложившаяся к середине XVIII в. единая оборонительная система включала в себя Ишимскую, Иртышскую и Колывано-Воскресенскую линии военных укреплений. Они протянулись более чем на 2000 верст с запада на восток от правого берега р. Тобол через междуречье Тобола, Ишима, Иртыша, далее на юго-восток вдоль Иртыша до крепости Усть-Каменогорской и затем — в северо-восточном направлении через Бийскую крепость до крепости Кузнецкой, опоясывая южные границы Западной Сибири.
В начале 40-х гг. XVIII в., в связи с вторжением джунгарских войск на территорию казахских степей и установлением протектората Джунгарии над Средним Жузом, возникла реальная угроза безопасности южных рубежей России. Поэтому в сентябре 1744 г. правительство принимает решение об укреплении границ и значительном усилении регулярных войск в Западной Сибири. В целях реализации этого решения в 1745 г. на сибирские линии были передислоцированы два пехотных и три конных полка под командованием генерал-майора Х. Т. Киндермана. В мае в Тобольск прибыли Нотебургский и Ширванский пехотные полки. Несколько позже из Казанской губернии подошли Вологодский и Луцкий драгунские, а из-под Нижнего Новгорода Олонецкий драгунский полк. Эти войска были расквартированы, главным образом, по крепостям Сибирской линии. Отдельным подразделениям некоторых из этих полков летом предстояло принять участие в строительстве Ново-Ишимской (Горькой) пограничной линии, большая часть которой пролегала по территории современного Северного Казахстана. Возведение новой линии впереди старой — Ишимской («чрезвычайно ломаной» и требующей значительной затраты сил и средств для обслуживания) являлось одной из мер по укреплению границ. Возведение новой линии началось летом 1752 г. после личного обследования генерал-майором Киндерманом предполагаемой для строительства трассы и окончательного утверждения проекта Указом Сената 26 марта 1752 г.
Строительство длилось до 1755 г. Согласно проекту, новая линия должна была состоять из двух шестиугольных и девяти четырехугольных крепостей, 33 редутов и 42 маяков. Однако к концу XVIII в. на Ново-Ишимской линии числилось 9 крепостей и 16 редутов.
На территории современной Северо-Казахстанской области располагались следующие из них: редут Пресногорьковский (ныне с. Пресноредут), крепость Кабанья (с. Кабанье), редут Пресноизбной (с. Екатериновка), крепость Пресновская (пос. Пресновка), редут Болотоколодезный (с. Новорыбинка), редут Саржанский (с. Сенжарка), редут Дубравный (с. Дубровное), крепость Становая (с. Становое), редут Гагарий (позже перенесен), редут Скопин (с. Маяк), крепость Святого Петра (г. Петропавловск), редут Плоский (с. Плоское), крепость Полуденная (с. Полудино), редут Медвежий (с. Медвежка), редут Чистый (с. Чистое), крепость Лебяжья (с. Лебяжье). Строительством этих укреплений было положено начало первым населенным пунктам на территории Северного Казахстана, некоторым из которых предстояло в скором времени стать центрами приходской православной жизни.
Строительство укреплений осуществлялось силами регулярных и нерегулярных войск — выписных казаков. Вместе с регулярными войсками на вновь возводимую линию прибыло и православное духовенство. Еще в начале XVIII в. организатор российской армии и флота император Петр I повелел «быть священнослужителям при каждом полку и корабле». В соответствии с «Воинским Уставом» 1716 г. назначение священнослужителей к воинским частям стало регулярным. Русская Православная Церковь с самого начала своего существования являлась духовной наставницей воинства и военному духовенству по праву принадлежала особая роль в русской армии. Хотя военные священники не принимали непосредственного участия в боях с оружием в руках, их оружием было Слово Божие. Они отправляли религиозные обряды, нравственно воспитывали личный состав, просвещали молодое пополнение — помогали скорее вступить в строй, провожали увольняемых в запас, с должным почтением провожали в последний путь погибших за Отечество на поле брани.
Военные священники дислоцированных в крепостях и редутах Ново-Ишимской линии конных и пеших полков были первыми представителями Русской Православной Церкви в Северном Казахстане. Именно они совершали молебны при закладке военных укреплений, а потом и духовно окормляли их строителей и стражей.
С завершением строительства в крепостях и редутах началась гарнизонная жизнь, связанная с организацией военной защиты государственных рубежей. Во второй половине XVIII в. каждый полковой священник состоял в ведении и под управлением того Преосвященного, в епархии которого квартировал его полк. В соответствии с существующим в то время церковно-административным делением военные укрепления Ново-Ишимской (Горькой) линии находились под юрисдикцией епархии Сибирской и Тобольской с центром в г. Тобольске.