А в это время в Тифлисе носились самые разные слухи по поводу того, кто придет на место М.С. Воронцова. Прошел даже слух о том, что наместником будет младший брат Василия Иосифовича генерал-лейтенант Давид Бебутов. Но Василий Иосифович в это не верил. Он трезво оценивал ситуацию, понимая, что это должен быть человек авторитетный, которого хорошо знал император, скорее всего, не новичок на Кавказе. Конечно, ему было не все равно, кого император назначит наместником и главнокомандующим Отдельным Кавказским корпусом. От этого зависело, как у него сложатся отношения с новым начальником.
Наконец стало известно, что вместо М.С. Воронцова наместником и главнокомандующим Отдельным Кавказским корпусом назначен генерал-адъютант Николай Николаевич Муравьев. Многие одобряли этот выбор, воспринимая его как человека, хорошо знавшего Кавказ. Люди по достоинству оценили выбор императора. Николай Николаевич длительное время провел на Кавказе, хорошо знал не только местные условия, проблемы, но и турок. Здесь он провел не один год, участвовал в боевых действиях, брал Карс. В.И. Бебутов данное известие встретил с облегчением. Как-никак, а Н.Н. Муравьева он не только хорошо знал как порядочного, уравновешенного человека, грамотного военного. В свое время в молодости и в последующем у них сложились добрые, приятельские, даже дружеские отношения, которые никогда ничем не омрачались.
Все с нетерпением ждали приезда генерала Муравьева в Тифлисе. Но тот сюда не спешил. По поступившим сведениям было известно, что он предварительно до приезда в Тифлис решил осмотреть Северный Кавказ, через который проезжал, расположенные там войска, познакомиться с командным составом.
Приехав в феврале 1855 г. в Ставрополь, он отсюда начал знакомство с краем. Наместник дотошно, со знанием дела осмотрел войска и укрепления на Кавказской линии, дороги, казачьи станицы, госпитали, присутственные места.
Приезд в Тифлис нового главнокомандующего Отдельным Кавказским корпусом и наместника на Кавказе Н.Н. Муравьева, которого все ждали с нетерпением и готовились к нему, оказался не радостным, а печальным. При подъезде к Тифлису генерала Н.Н. Муравьева догнал фельдъегерь из Петербурга, передавший пакет, в котором сообщалось о смерти 17 февраля 1855 г. императора Николая I. Это известие очень опечалило Николая Николаевича. Поэтому он въехал в Тифлис мрачным, что сразу вселило страх в окружающих. Зайдя в дом наместника, он никого не принял, а сразу отправился к патриарху.
На следующий день 2 марта на Александровской площади Тифлиса при огромном стечении народа и войск был прочитан манифест о смерти императора, принесена присяга новому императору Александру Николаевичу и совершено молебствие с коленопреклонением.
После этого у наместника началась работа. Н.Н. Муравьев во все старался вникнуть как можно быстрее и глубже. Он считал необходимым заставить всех работать интенсивнее. Разбираясь с делами, он видел, что замещавший князя Бебутова в гражданском управлении генерал Реут не справляется со своими обязанностями. Поэтому генерал Муравьев принял решение немедленно отозвать с театра военных действий генерала Бебутова, чтобы тот занялся делами гражданского управления, а самому вступить в командование действующим корпусом. Тем более что перед ним стояла важнейшая задача – как можно быстрее овладеть крепостью Карс.
5 мая 1855 г. генерал Муравьев писал военному министру князю Долгорукову: «Предполагая вслед за сим отправиться на Кавказско-Турецкую границу и вступить лично в командование войсками, там собранными, я признаю необходимым поручить доверенному лицу, на время отсутствия моего из Тифлиса, командование войсками Отдельного Кавказского Корпуса, не входящими в состав Действующего Корпуса на Кавказско-Турецкой границе. Все распоряжения и мероприятия ген.-л. кн. Бебутова во время командования им с осени 1853 г. Действующим Корпусом заслуживают полного одобрения, а славные победы, одержанные теми войсками над Турками в течение этой войны, свидетельствуют о военной опытности и предприимчивости кн. Бебутова. Несмотря на всю пользу, которую он принес бы и дальнейшим начальствованием над Действующим Корпусом, я буду принужден, по прибытии моем в Александрополь, отпустить его в Тифлис, дабы, по доверию моему к нему, к военной его распорядительности и знанию края, поручить ему на время отсутствия моего из Тифлиса командование войсками Отдельного Кавказского Корпуса, не входящими в состав Действующего Корпуса.