До постройки русских крепостей в степи, на южной границе Западной Сибири существовала укреплённая линия, построенная ещё во 2-ой половине ХVII века и носившая название Ишимской. Она шла от реки Миас через Курган, Коркину слободу (ныне г.Ишим) до Чернолуцкого острога на Иртыше (в 50 км севернее Омска). Эта линия была сильно извилистой и глубоко вдавалась во внутрь Сибири. Её длина простиралась до 1000 вёрст, на ней было 54 укреплённых пункта: остроги, форпосты и укреплённые рогатками селения. В 1744 г. на ней находилось незначительное число войск — 3406 человек при 63 пушках. В 1745 г., в связи с джунгарскими опустошениями казахской степи и возникшей опасности такого же опустошения Сибири, из Европейской России в Сибирь прибыло на постоянное квартирование пополнение: 2 пехотных и 3 драгунских полка. Количество войск на Ишимской линии увеличилось.
Старая Ишимская линия была слишком растянутой. Через неё проходили коммуникации Иртышской линии и Кузнецко-Колыванских укреплений. В связи с джунгарскими набегами стал вопрос о сокращении коммуникационной линии с Иртышем — о выпрямлении Ишимской линии, переносе её на юг, что значительно сокращало расстояние от реки Тобол до реки Иртыш.
В 1740-ых годах были отстроены Оренбургская и Уйская укреплённые линии. Они лежали значительно южнее Ишимской. С их устройством Ишимская линия, если бы оставалась не перенесённой на юг, оказалась бы наиболее слабой частью степных укреплений. Её форпосты находились на значительно большем расстоянии друг от друга, нежели на Оренбургской и Уйской линиях.
Сибирское командование, ещё при постройке Оренбургской линии, составило проект переноса Ишимской линии, который несколько раз пересматривался. 6 марта 1752 года последовал указ Сената о стpoительстве Новой Ишимской линии от урочища Звериная Голова на Тоболе до Омской крепости, протяжением в 565 вёрст. К постройке наметили11 крепостей, 33 редута и 42 маяка. Крепости строились на расстоянии 50-55 вёрст друг от друга. Редуты строились между крепостями на расстоянии 9-18 вёрст друг от друга, а маяки между редутами на расстоянии 4-8 вёрст. Крепости отличались от редутов большей величиной. Когда они были построены, их вооружили пушками (от 2 до 6 пушек), и гарнизон каждой из них состоял из 60-80 человек (кроме Петропавловской, где было значительно больше). В редутах имелось по одной пушке, и гарнизон состоял из 24-44 человек. На маяках (наблюдательных вышках) не было постоянного гарнизона, их обслуживали редуты.
Для строительства линии нарядили из тамошних войск 3642 человека. Указ Сената строительство Новой линии мотивировал как военными соображениями, так и тем, чтобы казахский народ «содержан был в подданической должности».
Летом 1752 года на всех местах намеченных крепостей и редутов приступили к строительству. Для работ использовались солдаты Вологодского полка и казаки Ишимского нерегулярного полка. 12 июля 1752 года на Ишиме, на 180 км. южнее старой линии, была заложена главная крепость Новой линии – «крепость святого Петра», как обычно сокращённо называли её в ХVIII веке. Более же пространное название – «Петропавловская». Почему она получила такое название? Культ Петра и Павла давно распространился в русской церкви, как культ покровителей войска. В старых русских городах, например, в Новгороде, среди казарм строились церкви в честь Петра и Павла. Такая же церковь была построена и в Петропавловской крепости в 1766 г. Неудивительно, что пять крепостей в разных районах империи, от Петербурга до Камчатки, в ХVIII — начале XIX века были названы именами Петра и Павла.
Начальником строительства Петропавловской крепости был назначен поручик Трейблут. В июле 1752 г. на постройке крепости было занято 97 человек. К 17 октября 1752 г. в крепости отстроили: временные бревенчатые стены, 4 батареи, ворота с башней, штабной дом, офицерскую светлицу, 10 казарм, 2 провиантских магазина, пороховой погреб, рогатки, малые батареи. Возле крепости построили конюшню на 120 лошадей. Со старых ишимских форпостов в новые крепости и редуты перевезли скудную артиллерию. На долю Петропавловской крепости досталось 5 пушек.
На следующее лето строительство продолжалось. Предстояло ещё много дел — были не готовы некоторые бастионы и совсем не начато устройство земляного вала, который должен был заменить бревенчатые стены. Земляные работы затянулись надолго, строительство замедлилось. В 1756 г. не были ещё готовы несколько батарей, 12 казарм, пороховые погреба. В 1765-1772 годах шли крупные земляные работы по устройству вала, на которые употреблялись арестанты-колодники. В 1769 г. на работе было занято 167 колодников, в 1772 г. — 97. В это время крепость была обведена и рвом.
По сравнению с другими укреплениями Ишимской линии, Петропавловская крепость производила более внушительное впечатление. Этим она была обязана своему положению на высоком правом берегу Ишима у излучины, круто поворачивающей течение реки. Бревенчатая стена (а позднее и земляной вал) имела форму шестиконечной звезды, в углах которой находилось 6 бастионов, два из них выходили на Ишим.
Первоначально ширина крепости между стенами равнялась 72 саженям. Наибольшее расстояние между внутренними углами двух противоположных бастионов определялось в 103 сажени. Внутри крепости находились деревянные постройки: штабной дом, офицерские светлицы, казармы, пороховые погреба, провиантские магазины и у ворот две кордегардии (караульные помещения). Крепостные ворота были устроены в башнях. Башни имели название: одна называлась Тобольской, другая — Омской.
В 1771 г. через крепость проезжал академик Фальк. Он оставил описание, которое не соответствует её первоначальному виду. Он отметил, что крепость имела в поперечнике 150 сажен. Очевидно, она к этому времени была расширена. Вместо бревенчатой стены, Фальк уже застал земляной вал, высотою в 12 футов с пятью воротами и башнями. На валу стояло 12 пушек. Вокруг вала шёл ров, наполненный водой. За рвом находились рогатки и надолбы. Вне крепости размещались две конюшни, кладовые, амбары, лазарет.
Рядом с крепостью располагались предместья: на горе — верхний, под горой — нижний форштадты. Они, в свою очередь, были обнесены рогатками и палисадом. На нижнем форштадте находилось двое ворот: Орские и Степные.
Окончательно Петропавловская крепость была отстроена к концу 70-ых годов ХVIII века. Она стала главной крепостью Новой Ишимской линии и опорным пунктом русского влияния в североказахстанских степях.
Первые годы существования крепости едва не омрачились бессмысленными мероприятиями, придуманными недалёким и трусливым сибирским военным начальством, назначавшимся во второй половине ХVIII века почти исключительно из прибалтийских немецких баронов — верной опоры самодержавия.
Начальство, желая показать своё усердие перед престолом, отправляло в Петербург донесение за донесением о предполагаемых нападениях казахов на степные линии и постоянно напоминало об этом линейным командирам. На самом же деле казахи по отношению русских укреплений вели себя мирно. Единичные случаи нападений казахов на русские гарнизоны вызывались грабительскими действиями и притеснениями линейных командиров. Некоторые казахские старшины, в расчёте на подарки, делали ложные доносы линейному командованию о якобы предстоящих нападениях казахов. Командование верило этим пустым сообщениям. После одного такого ложного доноса, командир Сибирского корпуса Крафт в 1755 г. додумался до следующего нелепого решения. Он приказал линейным командирам все казённые строения, лежащие вне укреплений, перенести во внутрь их, а частные постройки «вовсе без остатку сломать». Делалось это с целью усиления обороноспособности укреплений. И вот по всей Новой линии, от Тобола до Иртыша, началось уничтожение частных жилищ. Собранное с большим трудом на линию гражданское население осталось без крова. Такая же участь ожидала и Петропавловскую крепость. Вблизи неё, на горе и под горой, находилось 82 частных дома, где жили семьи военных чинов, служители, мастеровые люди и маркитанты (продавцы вина), всего 397 человек.
Командир Петропавловской крепости, несмотря на строгий приказ Крафта, проявил благоразумие и не решился уничтожить частные строения. Невозможно было перенести и наружные казённые строения в крепость. Она была тесна и не смогла бы вместить в себя стоявшие снаружи конюшни и лазарет. Командир доносил Крафту: «Хотя объявленное частное строение и вовсе сломать надлежало, точию тех людей 397 человек в одну крепость и состоящие казармы уместить никак невозможно, да и к тому же и опасно: по такому многолюдству от беспрестанного печения хлебов и варки пищи, печи, кои из глины биты, не могут своей препорции сдержать». Командир придумал иной выход. Он обнёс надолбами и рогатками наружные строения. Крепостные предместья — основа будущего города — не оказались стёртыми с лица земли.