Предполагалось, что на строительстве в течение двух лет ежедневно будут задействованы 1000 саперов, 7000 солдат и 1000 лошадей. Для руководства работами по возведению крепости Брест-Литовск были сформированы строительный комитет во главе с генералом Малецким и инженерная команда под началом капитана Вильмана. Однако вспыхнувшее в Польше восстание сорвало плановые работы, вынудив бросить все силы на сооружение полевых укреплений вокруг города и усиление Брестского замка.

После того как на престол взошел Николай I, внутренняя политика империи претерпела кардинальные изменения: от космополитизма и борьбы с «русским национализмом» правительство ударилось в противоположную крайность под лозунгом «Самодержавие. Православие. Народность». Новый монарх хотя и короновался польским королем, но «поляков и жидов» откровенно не любил. Началась планомерная русификация политической, общественной и культурной жизни западных губерний. Резко ограничивались права униатской церкви, которой «рекомендовалось» вернуться в лоно православия, упразднялись привилегии, дарованные предыдущими императорами. Осенью 1830 г. в Варшаве распространились слухи о том, что император планирует использовать польскую армию для подавления революции во Франции и Бельгии. 17 ноября началось восстание, которое распространилось по всей Польше. Сейм объявил о низложении династии Романовых и отделении от России, провозгласив главой правительства Адама Чарторыйского, а главнокомандующим с диктаторскими полномочиями генерала Хлопицкого, уступившего этот пост князю Михаилу Радзивиллу. Великий князь Константин Павлович под охраной гвардии оставил Варшаву и сам отпустил оставшиеся верными присяге превосходно обученные польские полки.

В короткий срок все Царство Польское было очищено от русских войск. Лишь в районе Белостока и Брест-Литовска оставался Литовский корпус генерала Розена. На помощь ему были двинуты Гренадерский корпус князя Шаховского и I корпус графа Палена. Поспешные, неудачные действия принявшего общее командование фельдмаршала И.И. Дибича, который рассчитывал провести молниеносную кампанию и пренебрег обеспечением тылов, а также эпидемия холеры, косившая солдат тысячами, поразившая самого главнокомандующего и великого князя Константина, привели к тому, что в апреле 1831 г. восстание перекинулось на территорию Литвы, Волыни и западной Беларуси. Однако здесь оно не получило поддержки городского населения и крестьянства и широкого размаха не имело. Брест-Литовск был обложен повстанцами, но горожане к ним присоединиться отказались. Город деятельно готовился к обороне и успешно отбил один нерешительный приступ. К августу волнения были подавлены на всей территории Беларуси, а 26 сентября русская армия под командованием генерал-фельдмаршала И.Ф. Паскевича после 36-часового штурма овладела Варшавой. В октябре Польша была окончательно усмирена. Результатом поражения восстания стали упразднение конституции, сейма, отдельной польской армии, введение российского территориально-административного деления. Граф Паскевич был назначен наместником в Царстве Польском и главнокомандующим прикрывавшей западное направление 1-й армии в составе I–IV «действующих» корпусов. Отдельный Литовский корпус был переименован в VI пехотный.

Эти события послужили дополнительным толчком к скорейшей реализации плана строительства Брест-Литовской крепости. С целью пересмотра и внесения поправок ее проект вновь попал в руки генерала К.И. Оппермана. Но уже в 1832 г. правительство потребовало, не дожидаясь утверждения детальных чертежей, приступить к заготовке необходимых материалов, для чего было от-пущено 500 тысяч рублей. Общее руководство работами поручили командиру Западного инженерного округа генерал-майору И.И. Дену. Высший надзор за ходом строительства был возложен на фельдмаршала Ф.И. Паскевича.

Генерал-инженер И.И. Ден (1787–1859)

Как уже говорилось, проектов имелось несколько, но Николай I выбрал самый радикальный: крепость было решено возвести на территории старого города, снести все мешающие постройки и стены старого замка и переселить жителей. Исторический Брест с его 800-летней историей подлежал полному уничтожению. Скорее всего это решение было принято как минимум на год раньше — слишком вольготно обращался с «подведомственным городом» барон Розен. Из предписания командира корпуса гродненскому губернатору следует, что к сооружению «крепостных укреплений и зданий» на месте жилой застройки приступили еще в мае 1830 г. Тогда же были произведены обмеры каменных монастырей и костелов «для переоборудования зданий с целью помещения учреждений другого назначения». Согласно рапорту брестского городничего от 24 августа 1831 г., при подходе к Бугу мятежнических войск солдатами VI корпуса «сверх прежде сломанных при оборонительных укреплениях обывательских в г. Бресте домов 83 сломано таковых же по волынскому форштадту 8». В 1833 г. Николай I внес собственноручные изменения в проект Оппермана и окончательно утвердил его.

Польский автор сокрушался: «…царь Николай I готовил городу гибель. Ни одно неприятельское нашествие не уничтожило так основательно древний град с его прекрасными памятниками старины, как уничтожил его император России. Он дал приказ разрушить город и вместо него построить оборонную фортификацию. От какой опасности она должна была защищать русское государство? От порывов свободолюбивых литовцев и поляков?.. Стоило ли разрушать и уничтожать материальное достоинство и культурные достижения, добытые многими поколениями?»

Началось строительство четырех временных укреплений. Центральное укрепление, или Цитадель, возводилось на месте торгово-ремесленного центра города. Волынское, или Южное, укрепление сооружалось на месте древнего детинца, где находился Брестский замок, предназначенный к сносу. Кобринское, или Северное, укрепление строилось на месте Кобринского предместья, где находились усадьбы горожан. Наконец, Западное, или Тереспольское, укрепление должно было разместиться на левом берегу Западного Буга на территории местечка Тересполь, где также решено было выселить жителей и разрушить их дома.

В июне 1833 г. развернулись земляные работы, продолжавшиеся пять лет. Тысячи солдат и согнанных на строительство крестьян, а также участники восстания проделали огромную работу, вручную перекопав и перенеся сотни тысяч кубометров земли, насыпав валы и прорыв каналы. Уже в декабре 1833 г. в Брест-Литовск из Киева была переведена гарнизонная артиллерийская рота, а через полгода из Варшавы прибыл гарнизонный батальон. В ночь с 31 мая на 1 июня 1835 г., за четыре месяца до посещения города Николаем I, в Брест-Литовске весьма своевременно вспыхнул очередной пожар, уничтоживший более 300 строений и позволивший ускорить расчистку территории будущей крепости. Сильно пострадали и были разобраны монастырь августинцев, католический костел и Свято-Николаевская церковь, в которой была подписана Брестская уния, а также знаменитая на всю Европу синагога. Погорельцы получали денежную компенсацию, но отстраиваться на прежнем месте уже не имели права. Согласно Положению от 27 июня 1834 г. новый город было предписано ставить в 2 км «северо-восточнее гласиса крепости», на правом берегу Мухавца в Кобринском предместье.