В ходе переговоров в Париже о заключении мира между Россией и державами, с которыми она воевала, предполагалось, что Россия передаст Турции Карс в обмен на Севастополь. Генерал Муравьев, находившийся на Северном Кавказе, 15 марта направил письмо князю Бебутову, в котором писал о том, что его брат Михаил, обеспокоенный делами на Кавказе, сообщал, что близится подписание в Париже мира и предполагается отдать Турции Карс. По этому поводу Михаил спрашивал у брата: «Неужели ты не уничтожишь, по крайней мере, Карсских укреплений, как они взорвали наши Севастопольские». Муравьев писал, что он лично поручил командующему корпусом генералу Хрулеву срыть Карсский укрепленный лагерь, начальнику штаба корпуса генералу Индрениусу указал, что именно уничтожить, а что оставить. Поэтому командующий просил князя Бебутова подтвердить это распоряжение письменно, с тем «чтобы приступить к сему делу при первой возможности, т. е. при стаянии снегов, начав срытие с предназначенных к уничтожению».
После взятия Карса генерал Муравьев, уведомляя военного министра Долгорукова о Карсских укреплениях, предложил их уничтожить и срыть. Император Александр II поддержал предложение, учитывая, что близилось завершение войны и России, возможно, предстояло возвратить Карс туркам. 14 марта военный министр сообщил Н.Н. Муравьеву, что император дал указание, чтобы «уничтожение Карсских укреплений приведено было в исполнение в возможно скорейшее время». Поэтому министр просил ускорить работы. Одновременно он потребовал немедленно представить ему сведения о том, что уже сделано по срытию укреплений.
Н.Н. Муравьев поручил генералу Бебутову ускорить работы по уничтожению крепостных укреплений, сделав на этот счет соответствующие распоряжения. Князь Бебутов, в свою очередь, поручая это сделать командующему действующим корпусом генералу Хрулеву и исходя из огромного объема работ, предписал использовать для ускорения уничтожения крепостных сооружений не только солдат, но и жителей города. Одновременно он потребовал ускорить вывоз из Карса казенного и артиллерийского имущества, захваченного в Карсе в качестве трофеев.
Насколько своевременны были эти действия, показало сообщение 22 марта генералу Муравьеву от военного министра о том, что мир в Париже подписан и согласно ему Турции должна быть возвращена Карсская область: «Предвидя наступившую ныне необходимость эту, я уже просил вас сообщить мне, в каком виде Карсская крепость находится в настоящую минуту, взорваны ли, хотя отчасти, построенные Англичанами и Турками верки и повреждены ли они, по крайней мере, весенним разливом вод. Ответа вашего я ожидаю с нетерпением, ибо в. выспр. изволите согласиться, что в виду Севастополя, совершенно разрушенного, было бы прискорбно уступить неприятелю завоеванные у него укрепления в неприкосновенной целости».
Таким образом, из этого видно, что руководство России было заинтересовано в том, чтобы Карсская крепость была возвращена с наибольшими разрушениями. Этого хотели и войска на Кавказе. Поэтому Н.Н. Муравьев снова дал указание князю Бебутову всемерно ускорить работы, пока не опубликован текст договора, направляя на их производство усиленные наряды населения и все наличные силы военных.
В свою очередь, турки, обеспокоенные тем, что в крепости Карс идут работы по демонтажу укреплений, направили к русскому командованию на Кавказе своего представителя для выяснения вопросов в связи с этим.
12 марта 1856 г. в Тифлис прибыл посланец Селим-паши мирливу Сеид-Хамди-паша для того, чтобы уточнить вопросы, связанные с определением, где будут находиться после заключения перемирия русские и турецкие посты. Поскольку Муравьев в это время выехал на Кавказскую линию, то принимал его генерал Бебутов, который не стал глубоко вдаваться с ним в переговоры. Используя свою обаятельность, он обласкал турецкого посланца Сеид-Хамди, устроив пышный прием, значительно усыпив его бдительность, и сделал более покладистым. В ходе проведенных переговоров они договорились по всем вопросам. После этого князь Бебутов отправил его 17 марта в Эрзерум с приветливым посланием для Селим-паши, в котором сообщал о посланных с такими же полномочиями русских офицерах. Таким образом, генерал Бебутов сделал все для того, чтобы затянуть переговоры.
А работы по уничтожению крепости Карс шли крайне медленно. Начальник Карсской области полковник Лорис-Меликов 8 апреля доносил командующему действующим корпусом, что хотя и приступили к срытию верков и других укреплений в крепости, но сделать это быстро невозможно, так как во рвах лежали глыбы льда, а оттаявшая земля пропитана водой настолько, что невозможно работать. Но, исходя из требования военного министра о том, что в виду разрушения Севастополя «было бы прискорбно уступать неприятелю завоеванные у него укрепления в неприкосновенной целостности», генерал Бебутов дал указание генералу Хрулеву, невзирая ни на что, немедленно приступить к работам.
17 апреля снова приступили к разрушению карсских укреплений. Однако здесь пришлось столкнуться еще с одной трудностью. Жители с большой неохотой выполняли требования русского начальства, да и то под большим нажимом. Помимо этого, они отправили турецкому правительству жалобу на это распоряжение. В связи с этим генерал Хрулев обратился с просьбой работы по разрушению укреплений прекратить и оставить их в том виде, в каком они находились. Он также сообщал, что для взрыва цитадели направил инженера полковника Пашканга. Поскольку генерал Бебутов данного вопроса без наместника решить не мог, то, не давая приказа о прекращении работ, 27 апреля обратился к Муравьеву, находившемуся на Кавказской линии, испрашивая согласия прекратить разрушение укреплений и не назначать жителей на эти работы.
К этому времени, согласно заключенному миру, многое уже было ясно. Россия возвращала Турции Южную Бессарабию. Российское правительство также обязано было возвратить Турции крепость Карс и область. Поэтому правительство сочло за лучшее не уничтожать укрепления Карса, чтобы Россию не обвинили в нарушении договора.
Повеление о прекращении работ по срытию укреплений в Карсе было получено 4 мая. Но к этому времени, пользуясь установившейся погодой, многое было сделано: срыты все верки, ранее занимавшиеся турецкими войсками над господствовавшими над городом высотами, пороховые погреба и блокгаузы разрушены. Кроме того, было срыто большое укрепление, известное как кладбищенское на левом берегу реки Карс-чая. В цитадели, состоявшей из трех ярусов, верхний ярус, представлявший башню на 8—10 орудий, был обрушен взрывами. Второй ярус представлял собой стену с амбразурами и башню на 4 орудия. В нижнем ярусе три пороховых погреба были взорваны, а в трех разобраны крыши.
После заключения Парижского мира нужно было решить много вопросов в Закавказье, связанных с возвращением территорий Турции, а также присоединенных к России территориий и занятия русскими войсками Сухума и Редут-Кале. Князь Бебутов, докладывая генералу Муравьеву о положении дел, писал относительно Абхазии: «Полагал бы я необходимым сперва определить положение правителя Абхазии кн. Ширвашидзе, к нашему правительству». Что касается Редут-Кале, предлагал расположить две роты не только в нем, но и в бывшем укреплении Николаевском.
После завершения Крымской войны