Поскольку Черевин стал "человеком команды" М.Н. Муравьева, то на его карьере отразились все интриги против его покровителя. А противники у Муравьева-Виленского имелись очень влиятельные. Главным из них был младший брат Александра II великий князь Константин Николаевич, после которого Муравьеву и пришлось "разгребать" политические "завалы" в Виленском крае. В записках Черевин незатейливо характеризовал Константина Николаевича как взбалмошного негодяя, мечтавшего только о популярности и польской короне для себя . Впоследствии отношение Черевина к великому князю Константину Николаевичу стало одной из основ для сближения генерала с наследником-цесаревичем Александром Александровичем. Сближало их и отношение к петербургским "партиям": "Что прочно в Петербурге? Ничто и никто, ни мнение, ни люди, ни системы… Сегодня Шувалов, завтра Милютин и в итоге не знаешь, чего хотят" . Поэтому, хотя М.Н. Муравьев неоднократно ("дважды в год") представлял Черевина к наградам, он получил только скромную корону к своему Св. Станиславу с мечами (в сентябре 1864 г.). Хотя Черевин и получил в 1864 г. чин подполковника, но представление исходило еще от наместника на Кавказе, великого князя Михаила Николаевича.
Те, кто видел Черевина в 1863–1864 гг. отмечали, что он находился при Муравьеве безотлучно. Поэтому, когда весной 1864 г. М.Н. Муравьев выехал в Петербург, мало кто удивился тому, что Черевин был оставлен "на хозяйстве" глазами и ушами Муравьева с задачей вести с ним постоянную переписку .
В Петербурге Муравьев фактически сдавал дела. Но и тогда он не забыл Черевина и во время аудиенции у Александра II "испрашивал у Государя особенную награду" для Черевина, как вариант, предлагая перевести Черевина в гвардию ротмистром. Александр II не дал четкого ответа, но попросил напомнить ему о Черевине при проезде его через Вильну.
Вскоре императорская чета прибыла в Вильну, где во время 30-минутной стоянки генерал-губернатор М.Н. Муравьев в числе высших должностных лиц управления краем представил Александру II подполковника П.А. Черевина. Император поблагодарил офицера за его службу. Это была первая личная встреча Черевина и Александра II. Однако эта высочайшая благодарность так и не вылилась для Черевина в какие-либо карьерные дивиденды. Поэтому в августе 1864 г. Черевин отпросился в отпуск по болезни за границу. М.Н. Муравьев согласился дать Черевину месячный отпуск, который он провел на море во Франции.
В своих записках по горячим следам в 1868 г., Черевин довольно высоко оценивал собственную деятельность в Виленском крае: "По роду занятий, сколько по громадности их, я считал себя и был вправе считать себя оскорбленным, когда многие другие, ничего не делавшие, награждались по два раза в год… Недоброжелательство к М.Н. Муравьеву распространилось и на меня" (видимо, обида была настолько сильна, что ее не сгладило даже назначение в 1867 г. флигель-адъютантом к Александру II. – И. 3.).
9 июля 1864 г. покровителя Черевина М.Н. Муравьева уволили от должности. В этой ситуации Черевин уже не видел в Вильно для себя никаких перспектив. Он выразил категорическое нежелание занять прежнюю должность. Весной 1865 г. Муравьев и Черевин обсудили карьерные перспективы последнего. Черевин заявил, что не планирует продолжение службы в Вильно и намерен взять продолжительный отпуск, после чего рассчитывает поступить в распоряжение военного министра. В конце апреля 1865 г. Черевин, получив отпуск, уехал в деревню. Вскоре он получил приказ о назначении "состоять по Военному министерству" и фактически к началу 1866 г. служебные перспективы подполковника Черевина выглядели довольно туманными. Трудно сказать, как бы сложилась судьба П.А. Черевина, если бы судьба не дала ему еще одного шанса.
4 апреля 1866 г. бывший студент Д. Каракозов совершил неудачное покушение на Александра II. В результате была немедленно организована Следственная комиссия, которую с 7 апреля 1866 г. возглавил М.Н. Муравьев. Возглавив следствие, М.Н. Муравьев включил в состав комиссии П.А. Черевина. И вновь за короткий срок Черевин сумел стать заметной фигурой в Следственной комиссии. В свои 29 лет он занял место секретаря комиссии, лично принимал участие в арестах членов кружка Худякова – Ишутина, активно участвовал в допросах. Усердие молодого полковника в расследовании важнейшего дела было замечено и отмечено. И несмотря на смерть 31 августа 1866 г. М.Н. Муравьева, карьера Черевина обрела "второе дыхание". В результате активная деятельность П.А. Черевина в расследовании покушения стала второй прочной ступенькой в его служебной карьере.
На протяжении жизни Черевин не раз добрым словом поминал своего покровителя. В феврале 1869 г. он писал: "…я служил при великом человеке… Школа, пройденная при нем, конечно, послужила и послужит мне во многом в будущем, и я с гордостью вспоминаю, что за время нахождения моего при гр. Муравьеве заслужил его любовь и доверие" .
После окончания следствия по делу Каракозова Черевин занял довольно прочное положение в Петербурге. Об этом свидетельствовало и то, что он в 1867 г. получил звание флигель-адъютанта Свиты Е.И.В., и то, что в мае 1869 г. его назначили командиром Собственного конвоя. Поскольку главная задача Собственного Е.И.В. конвоя было обеспечение личной безопасности императора, то эта должность была "на виду". В должности командира Собственного конвоя П.А. Черевин прослужил 10 лет – с 24 мая 1869 по 13 августа 1879 г. Все эти годы по должности командир Конвоя подчинялся командующему Главной Императорской квартирой генерал-адъютанту A.M. Рылееву.
Во время Русско-турецкой войны 1877–1878 гг. командир Собственного конвоя флигель-адъютант полковник П.А. Черевин в сентябре 1877 г. вступил во временное командование Кавказской казачьей бригадой, которая входила в состав отряда генерала И.В. Гурко. Это было очень характерное для Черевина перемещение. Он – храбрый кавалерийским офицер, и ему требовалось живое дело. Нужны были и орденские кресты. В качестве командира бригады он лично участвовал в атаке на защитников Горного Дубняка и взятии Телешских укреплений, переходил через Балканы.
На войне Черевин свел близкое знакомство с наследником-цесаревичем великим князем Александром Александровичем, будущим императором Александром III. Он привлек к себе внимание цесаревича своим веселым нравом, храбростью, прямотой и резкостью суждений, остроумием и находчивостью. Будущий царь ценил таких людей. С тех пор их связывали прочные отношения. Александр III до конца жизни покровительствовал ему и полностью полагался на своего боевого товарища.
За Русско-турецкую кампанию 1877–1878 гг. П.А. Черевин получил высокие награды: золотое оружие с бриллиантами, крест Св. Георгия IV степени и назначение в Свиту Александра II. В октябре 1878 г. он вновь ненадолго возглавил Собственный конвой . B.C. Кривенко описывал внешность Черевина на конец 1870-х гг. следующим образом: "В казачьей свитской форме, с георгиевским крестом за турецкую кампанию, в большой белой папахе на трясущейся слегка голове. Из под длинных завитушек курпея высматривают зорко-пронзительные колючие глаза. Лицо подернуто алкогольной окраской, острый нос, отвисшие вниз усы и шутливое приветствие на улыбающихся губах" .
В результате 10-летнее командование элитным воинским подразделением государственной охраны, участие в Русско-турецкой войне и сближение с наследником-цесаревичем стали важной ступенью в карьере П.А. Черевина.
К 1879 г. ситуация в стране кардинально изменилась. После очередного неудачного покушения на Александра II в апреле 1879 г. революционеры окончательно сделали ставку на террор. К лету 1879 г. складывается террористическая организация "Народная воля", начавшая энергичную подготовку серии террористических актов. Изменение ситуации в стране отразилось и на карьере П.А. Черевина. В августе 1879 г. П.А. Черевин сменил военный мундир на жандармский, став товарищем Шефа жандармов, начальником III Отделения СЕИВК и деятельным участником борьбы с революционным террором.
Отношение П.А. Черевина к III Отделению СЕИВК было более чем скептическим. Черевин сталкивался с деятельностью III Отделения еще в бытность службы в Вильно в 1863–1865 гг. и тогда он вынес самое неблагоприятное впечатление об этой силовой структуре. Еще задолго до своего назначения руководителем III Отделения, в январе 1868 г., он писал: "III Отделение с его служащими всегда являлись защитниками неблагонадежных не одних поляков, но и русских негодяев, как оно себя показало в деле покушения Каракозова" . Фактически Черевина назначили начальником III Отделения для того, чтобы он на его базе создал новое структурное подразделение МВД, способное эффективно противостоять революционерам-террористам.
1879–1880-е гг. были тяжелым временем для силовых структур империи. Сложившиеся в относительно спокойное и стабильное николаевское время, они "не успевали" за тактическими, организационными и техническими новациями "Народной воли". Силовым структурам требовалась "свежая кровь" из людей, которые могли адекватно реагировать на вызовы времени. Современники так и воспринимали Черевина – как "нового человека". Одна из мемуаристок писала в дневнике о П.А. Черевине в январе 1880 г.: "Из новых личностей Черевин не произвел на меня того впечатления, какого я от него ожидала: тихий на вид, умно смотрит" .