Польский автор сокрушался: «…царь Николай I готовил городу гибель. Ни одно неприятельское нашествие не уничтожило так основательно древний град с его прекрасными памятниками старины, как уничтожил его император России. Он дал приказ разрушить город и вместо него построить оборонную фортификацию. От какой опасности она должна была защищать русское государство? От порывов свободолюбивых литовцев и поляков?.. Стоило ли разрушать и уничтожать материальное достоинство и культурные достижения, добытые многими поколениями?»
Началось строительство четырех временных укреплений. Центральное укрепление, или Цитадель, возводилось на месте торгово-ремесленного центра города. Волынское, или Южное, укрепление сооружалось на месте древнего детинца, где находился Брестский замок, предназначенный к сносу. Кобринское, или Северное, укрепление строилось на месте Кобринского предместья, где находились усадьбы горожан. Наконец, Западное, или Тереспольское, укрепление должно было разместиться на левом берегу Западного Буга на территории местечка Тересполь, где также решено было выселить жителей и разрушить их дома.
В июне 1833 г. развернулись земляные работы, продолжавшиеся пять лет. Тысячи солдат и согнанных на строительство крестьян, а также участники восстания проделали огромную работу, вручную перекопав и перенеся сотни тысяч кубометров земли, насыпав валы и прорыв каналы. Уже в декабре 1833 г. в Брест-Литовск из Киева была переведена гарнизонная артиллерийская рота, а через полгода из Варшавы прибыл гарнизонный батальон. В ночь с 31 мая на 1 июня 1835 г., за четыре месяца до посещения города Николаем I, в Брест-Литовске весьма своевременно вспыхнул очередной пожар, уничтоживший более 300 строений и позволивший ускорить расчистку территории будущей крепости. Сильно пострадали и были разобраны монастырь августинцев, католический костел и Свято-Николаевская церковь, в которой была подписана Брестская уния, а также знаменитая на всю Европу синагога. Погорельцы получали денежную компенсацию, но отстраиваться на прежнем месте уже не имели права. Согласно Положению от 27 июня 1834 г. новый город было предписано ставить в 2 км «северо-восточнее гласиса крепости», на правом берегу Мухавца в Кобринском предместье.
До возведения крепости Брест имел 726 домов, один православный и шесть католических монастырей, синагогу, иезуитский коллегиум (одним из самых знаменитых его выпускников и преподавателей был воин-философ Казимир Лыщинский, сочинивший атеистический трактат «О несуществовании бога»), 12 приходских и монастырских церквей, магистратуру, гостиный двор, больницу, 160 торговых лавок.
