К моменту начала мятежа правителем Литвы и Беларуси на протяжении семи лет был В.И. Назимов, человек добрый и старательный, но уж очень нерешительный. При нем в крае буйным цветом расцвела антироссийская пропаганда. Православные подвергались оскорблениям со стороны польских обывателей. Когда из Царства Польского в Беларусь был «экспортирован» мятеж, Назимов шарахался от прямого попустительства инсургентам, как тогда называли повстанцев, до непоследовательных запретительных и репрессивных мер, которые, впрочем, не имели никакого действия.
Зимой-весной 1863 года в патриотических кругах все чаще стала называться фамилия Муравьева в качестве кандидата в виленские наместники. По воспоминаниям, решающее слово сказал мудрый канцлер А.М. Горчаков, рекомендовавший Александру II отважиться на подобное кадровое назначение. Государь лично пригласил Муравьева к себе 28 апреля 1863 года и через два дня назначил его виленским, гродненским и минским генерал-губернатором, командующим войсками Виленского военного округа с полномочиями командира отдельного корпуса в военное время, а также главным начальником Витебской и Могилевской губерний
Отъезд М.Н. Муравьева из Петербурга был обставлен как отправка былинного героя на битву. Митрополит, встретив его, промолвил: «Имя тебе — Победа!». Сам будущий граф помолился в Казанском соборе и приложился к чудотворной иконе Казанской Божьей Матери. По приезде же в Вильно Михаил Николаевич первым делом отправился поклониться мощам Св. Виленских мучеников в Духов монастырь, а затем к знаменитому митрополиту Иосифу Семашко, в свое время положившему конец униатскому безумию.
Новый генерал-губернатор начал с подбора команды. Прежние чиновники, продемонстрировавшие свою неэффективность, были отстранены. Муравьев сумел воспитать целую когорту блестящих администраторов и управленцев. Среди них следует отметить, прежде всего, попечителя Виленского учебного округа И.П. Корнилова, начальника тайной полиции ротмистра Шаховского, генералов Лошкарева, Соболевского, Панютина, полковников Макова, Черевина, Неелова, занимавшегося разбором судебных дел. К «муравьевской плеяде» можно отнести и К.П. Кауфмана, сменившего Михаила Николаевича на посту главного начальника Северо-Западного края. Впоследствии генерал Кауфман стал широко известен как покоритель Туркестана. Все это были верные сыны Отечества, благородные люди и достойные граждане.
В свои 67 лет генерал-губернатор установил и для себя, и для подчиненных ему чиновников беспощадный рабочий режим, который позволял максимум усилий тратить на развитие вверенного ему государем и Отечеством края. Михаил Николаевич вставал в 6 часов утра, в 7 часов он уже приступал к работе, занимаясь делами до пяти вечера, затем делал 4-часовой перерыв на обед и отдых и вновь работал до часа ночи.