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