Считая, что Ермолов не справляется со своей ролью главнокомандующего, Николай I приказом от 10 августа 1826 года послал на Кавказ генералов И. Ф. Паскевича и Д. В. Давыдова.
К тому времени, однако, военные обстоятельства переменились в лучшую сторону. Против Гассан-хана Ермолов отрядил полковника Муравьёва, а во главе передового отряда, выступившего навстречу Аббас-Мирзе, поставил генерала Мадатова. Сам он со слабым, в четыреста штыков, гарнизоном оставался в Тифлисе, страшась за свой тыл и возлагая надежду единственно на авторитет грозного своего имени.
3 сентября под селением Шамхор Мадатов наголову разбил десятитысячный персидский корпус: русские заняли Елисаветполь, персы сняли блокаду Шуши. Шамхорская победа была фактом, предрешившим исход войны; будущее обещало только новые и новые победы. Но время для Ермолова уже прошло — и безвозвратно. На сцене стоял Паскевич. 13 сентября вся огромная персидская армия была разгромлена кавказскими войсками под его руководством у Елисаветполя.
Своим успехом Паскевич был обязан ермоловским генералам и ермоловским солдатам. Храбрый генерал, он всю жизнь оставался баловнем судьбы. Когда впоследствии льстецы убеждали его отца, украинца, что у него сын гений, тот резонно заметил: «Що гений, то не гений, а що везе, то везе…» Увидев перед собой многотысячную тучу персидской конницы, Паскевич пришёл в смущение и хотел было отступить, однако Мадатов и Вельяминов настоятельно доказали ему необходимость принять сражение. По справедливому выражению одного из современников, «чepeз Елисаветполь Россия лишилась в Ермолове фельдмаршала с замечательными способностями». Теперь лавры дожали на голове Паскевича, руки его были развязаны, и он принялся в письмах Николаю I набрасывать на Ермолова чёрные тени. Впрочем, и до Елисаветпольского дела он пользовался полным доверием нового императора, который писал ему на Кавказ:
«Помнишь, когда мы с тобой играли в военную игру; а теперь я твой государь, и ты — мой главнокомандующий».
Победа вскружила ему голову. Мало знакомый со страной, Паскевич стремился перенести войну в пределы Персии. Ермолов на правах формального главнокомандующего не признавал это возможным до прибытия новых сил, и Паскевич обвинил его в зависти. Обидев интригами наместника, он сумел скоро оскорбить и войска своим высокомерным отношением. Накануне Елисаветпольского сражения Паскевпч учил их маршировке и перестроениям и, недовольный выправкой, говорил шамхорским победителям, что ему «стыдно показать их неприятелю». Воротившись в Тифлис, он занялся разводами и парадами, в которых боевые, закалённые в походах и сражениях кавказские солдаты были с петербургской точки зрения далеко не сильны.
После многолетних походов по горам Дагестана и лесам Чечни и Черкесии в Тифлис прибыл Ширванский полк — «десятый римский легион», как любовно называл его Ермолов, по аналогии с войском Цезаря. Весёлые, бодрые, уверенные получить похвалу, проходили ширванцы мимо дома главнокомандующего, с балкона которого смотрел на них Паскевич. Вглядевшись в одежду солдат, из которых многие носили шаровары вместо панталон и были в лаптях или азиатских чувяках, Паскевич пришёл в такое негодование, что прогнал полк с глаз долой. Уже готовился грозный приказ по корпусу с объявлением строжайших взысканий полковому начальству, когда вмешался Ермолов. На правах главнокомандующего он отдал другой приказ, в котором горячо благодарил Ширванский полк за оказанные им в боях чудеса храбрости и за твёрдость в перенесении трудов и лишений, выпавших на его долю.
Паскевич не ограничился одними только военными вопросами, считал себя вправе вмешиваться в управление делами, всюду разыскивая злоупотребления и ошибки. Он ловил слухи и сплетни от самых подозрительных лиц, чернил Ермолова, его военную репутацию, намекал на его политическую неблагонадёжность и порицал ермоловских помощников, в том числе Малахова и Вельяминова, которым был обязан победой под Елисаветполем.
Ермолов болезненно и тяжко переживал происходящее.
Разорялось так заботливо создаваемое им русское гнездо на Кавказе, ломались налаженные и, казалось бы, незыблемые служебные положения лиц из ближайшего окружения (братьев Вельяминовых, Мадатова, Муравьева, рассчитывавшего обосноваться там Дениса Давыдова), уничтожение грозило суворовским порядкам, введённым в Отдельном Кавказском корпусе.
Доносы Паскевича между тем становились всё пристрастнее и начали смущать даже Николая I. Понадобилось третье лицо, чтобы распутать создавшееся положение. Воля царя вала на начальника главного штаба Дибича. Он получил самые широкие полномочия, вплоть до увольнения Ермолова. О приезде Дибича на Кавказ официально поставлен в известность был один Паскевич; наместник узнал об этом стороной.
В феврале 1827 года Ермолов вызвал к себе полковника Муравьёва, который застал главнокомандующего необычайно расстроенным.