По дороге майор П.А. Черевин заехал в Тифлис, где получил аудиенцию у Наместника края, великого князя Михаила Николаевича. Во время встречи великий князь расспрашивал Черевина «о последних бывших делах». Как боевого офицера, служившего ранее в лейб-гвардии Кавалергардском полку, его «удостоили приглашения к столу Его Высочества»442. Собственно, на этом закончился «кавказский этап» биографии П.А. Черевина. За эти годы он получил первый штаб-офицерский чин и боевой орден, приобрел бесценный боевой опыт в ходе Кавказской войны и при этом не растерял связей в петербургской гвардейской среде.
Хотя Черевин мыслил об отставке, тем не менее в глубине души 25-летний майор плохо представлял себя в роли провинциального помещика, поэтому, приехав в родовое имение «Нероново» под Костромой, он немедленно написал письмо Н.М. Муравьеву с изложением своих «обстоятельств».
В своих записках Черевин упоминает о том, что к этому времени он уже «хорошо знал» М.Н. Муравьева, который с 29 ноября 1862 г. вступил в должность генерал-губернатора мятежного Виленского края. Примечательно стремление Черевина, приехавшего в родовое имение с Кавказской войны, немедленно отправиться в Виленский край, где русские войска вели боевые действия с польскими партизанскими отрядами. Через 3 недели фельдъегерь привез Черевину предписание военного министра о немедленном отправлении в Вильну в распоряжении Командующего войсками округа и генерал-губернатора М.Н. Муравьева. В начале сентября 1863 г. П.А. Черевин оказался в Вильне, где начался новый важный этап его биографии.
Вряд ли кто из видевших тогда майора П.А. Черевина, прибывшего в Вильно в армейской форме Севастопольского полка, предполагал, что тот вскоре займет ключевое место в администрации края и станет правой рукой М.Н. Муравьева. Однако М.Н. Муравьев остро нуждался в преданных и инициативных подчиненных, на которых он мог бы положиться, да еще с опытом боевых действий на Кавказе. Поэтому он немедленно подключил П.А. Черевина к практической работе.
Поначалу П.А. Черевина назначили чиновником для особых поручений, состоящим при генерал-губернаторе. Его отправили в командировку в Ковенскую губернию в Вилькомирский и Поневежский уезды с целью сбора информации о деятельности должностных лиц против польских повстанческих отрядов. Там П.А. Черевин столкнулся как с неповоротливостью военной машины в целом, так и с безынициативностью отдельных начальников. Попытки рекомендовать им «кавказскую тактику» борьбы против польских партизанских отрядов сочувствия не встретили, поэтому по возвращении Черевин представил М.Н. Муравьеву «подробный и откровенный доклад о всем мною найденном»443.
Через неделю после возвращения Черевина из командировки его назначили заместителем генерал-губернатора по гражданской части. До 26-летнего майора Черевина эту должность занимал генерал-майор. Сам П.А. Черевин сравнивал свою должность «с должностью начальника штаба по гражданской части». Это назначение сразу определило степень влияния Черевина. По его словам, он просматривал всю служебную переписку, шедшую на имя Муравьева, по три раза в день делал личные доклады генерал-губернатору, фиксировал и начинал реализовывать устные резолюции Муравьева, распределял дела по канцеляриям, наблюдал за скорым и точным исполнением всех резолюций, вел секретную переписку и прием посетителей444. Столь стремительное возвышение Черевина не только привлекло к нему пристальное внимание, но и породило массу завистников, хотя деятельность Черевина в Виленском крае властные круги в целом оценивали положительно. Несмотря на молодость и малый чин, Черевин хорошо проявил себя и стал одной из заметных фигур при подавлении восстания поляков на северо-западе, в ходе которого его шеф получил прозвище «Вешатель». В «виленский период» Черевин на деле подтвердил свою репутацию храброго, инициативного и умного офицера. Например, спустя несколько десятилетий, видный чиновник Министерства двора B.C. Кривенко отмечал в воспоминаниях, что Черевин, еще будучи молодым кавалергардским офицером, «успел выделиться… и обратил на себя внимание Муравьева-Виленского. Свирепый усмиритель Польского восстания приблизил к себе Петра Александровича, использовал молодую энергию для проведения своей линии…». Мемуарист также подчеркивал незаурядные дипломатические способности Черевина. Будучи правой рукой Муравьева-Вешателя»445, он сумел «наладить свои личные отношения с поляками, видевшим в нем заступника перед проконсулом»446. Генерал Н.А. Епанчин, характеризуя Черевина, упоминает, что это человек «острого ума, имевший опыт в административных делах; недаром М.Н. Муравьев пригласил его, молодого полковника, на должность начальника канцелярии Виленского генерал-губернатора, когда Муравьев был назначен для усмирения Литвы»447.